The True History of Tea (Hoh / Mair) has a surprisingly comprehensive summary in the first chapter on other types of drinks (not just steeped leaf ones) consumed in early history. One I hadn't heard about was a drink made by Creek Native Americans by infusing the leaves of the yaupon holly.
They also mention various leaves that are masticated (such as Khat or Coca, both of which, according to Wikipedia, at least, have also been steeped in water, though I don't remember any mention of that in the book, and betel nut). They mention kava (traditionally masticated, spit out, and then mixed with water and strained).
They discuss guarana, which is a seed, rather than a nut, but which is eventually dissolved in cold or hot water, after being processed. And of course, coffee.