When you boil down the question, the appropriate answer hinges on what would have been meant by "herbal tea" prior to the introduction of the word 'tea' in the sense of
2. a. A drink made by infusing these [Thea (now often included in Camellia)] leaves in hot water, having a somewhat bitter and aromatic flavour, and acting as a moderate stimulant; largely used as a beverage.
["tea, n.". OED Online. March 2016. Oxford University Press. http://www.oed.com/view/Entry/198340?rskey=tnWhke&result=1&isAdvanced=false (accessed April 30, 2016).]
The word in forms resembling modern 'tea', and used in sense 2.a, that is, the drink as opposed to the plant, is not attested in OED Online until the mid-1600s (1658, 'Tcha', 'Tay', 'Tee'), earlier attested forms in English being 'Chia' and 'cha'.
If a meaning approximating what is encompassed by 'herbal infusion', that is, a specific process-oriented meaning, is intended, 'infusion' is not attested in that sense until, at the earliest, the mid-1500s (?1550). Note that uses of 'infusion' with that meaning refer to medicinal preparations made by steeping as opposed to boiling.
4. b. A dilute liquid extract obtained from a substance by soaking it with, or steeping it in, water; also any water containing dissolved organic (esp. vegetable) matter, such as that in which Infusoria are found.
["infusion, n.". OED Online. March 2016. Oxford University Press. http://www.oed.com/view/Entry/95690 (accessed April 30, 2016).]
Another specific process-oriented word might be 'decoction'. It is attested in 1398 in this sense:
4. A liquor in which a substance, usually animal or vegetable, has been boiled, and in which the principles thus extracted are dissolved; spec. as a medicinal agent.
["decoction, n.". OED Online. March 2016. Oxford University Press. http://www.oed.com/view/Entry/48312 (accessed April 30, 2016).]
As with 'infusion', 'decoction' was used with reference to specifically medicinal prepartions. As opposed to the steeping denoted by 'infusion', 'decoction' denotes boiling to obtain the preparation.
My nomination for the appropriate word to answer your particular question departs from process-oriented meanings in favor of a purpose-oriented meaning. The word was in use much earlier, but the evidence, its attestation from c1220-c1440, suggests it was perhaps obsoleted by the process-oriented words 'infusion' and 'decoction' in literate if not in common use prior to the introduction of 'tea':
† halewei | halewey, n.
A healing water, used both as a drink, and as a lotion for wounds; balm, antidote.
["† halewei | halewey, n.". OED Online. March 2016. Oxford University Press. http://www.oed.com/view/Entry/83398 (accessed April 30, 2016).]
Other authorities tend to cast 'halewey' as a particular kind of tea, rather than a generic term (healing water), although they differ on its composition:
(From Totally Weird and Wonderful Words, Erin McKean, Oxford University Press, Oct 23, 2006).
(From Selections from Early Middle English, Joseph Hall, Clarendon Press, 1920.)
Another good candidate than 'halewey', attested from before 1200 with documentary evidence dated around 1225 (dates uncertain), has a generic process-oriented meaning alternative to the purpose-oriented meaning of 'halewey':
† sabras, n.
A decoction or infusion.
?c1225 (▸?a1200) Ancrene Riwle (Cleo. C.vi) (1972) 268 Þe an for geað alþet he luued. of metes & of drunches. & drinkeð bittere sabraz forto acouren heale.
["† sabras, n.". OED Online. March 2016. Oxford University Press. http://www.oed.com/view/Entry/169377 (accessed May 01, 2016).]
As little is known about the composition of 'sabras' (variant 'sabrace') as about the composition of 'halewey', but it has been suggested that the word derives from an Arabic word for 'a drink':
In the Ancren Riwle, edited for the Camden Society by the Rev. J. Morton, p. 364, it is said that a sick man who is wise uses abstinence, and drinks bitter sabras to recover his health: in the Latin MS. Oxon. potat amara. It may be from the Arabic, "Shabra, a drink." See Notes and Queries, vol. ii. pp. 70, 204.
(From Promptorium Parvulorum Sive Clericorum: Dictionarius Anglo-Latinum Princeps, Volume 89, Sumptibus Societatis Camdenensis. This is an 1865 edition of the Promptorium Parvulorum, itself dated around 1440, edited and annotated by Albertus Way.)