After several sessions of struggling with my level 70 hunter to travel all the various Northrend zones in search of herbs and coming up mostly empty, I finally had the bright idea to use my premade PvP druid since he is level 80 and can fly over Northrend. That is a much easier way to find herbs rather than trekking through the aggro-crazy mobs on land as a level 70 noob. Alas, Mr PVP did not have any tradeskills, but a quick visit to the Herbalism trainer took care of that.
Armed with the ability to track herbs and an Herbalism skill of 1, I made my way to the Borean Tundra. Previously, I had done a full pass of this zone on my hunter and never found the elusive Firethorn. I was hoping that being on a PVP server instead of my normal PVE server would mean less rampant farming of nodes in the newbie zones so I could actually locate one this time. With my 80 druid I was able to locate all the missing herbs in about 20 minutes of traveling. And my low-level herbal skills turned out to be a bonus: Goldclover was yellow to my hunter at 375, so she was unable to see what skill it required. But my druid is too low for any Northrend herbs, so he learned that Goldclover requires 350 Herbalism.
Without further ado I give you: The Herbalism Skill List
Goldclover: Requires 350, found in Borean Tundra, Howling Fjord and Dragonblight
Firethorn: Requires 360, found in Borean Tundra (near the Geyser field only)
Talandra's Rose: Requires 385, found in Zul'Drak
Tiger Lily: Requires 400, found in Borean Tundra, Grizzly Hills, Howling Fjord and Sholazar Basin
Frozen Herb: Requires 415, found in Zul'Drak
Lichbloom: Requires 425, found in Storm Peaks and Icecrown
Adder's Tongue: Requires 430, found in Sholazar Basin (changed to 400 on Live server!)
Icethorn: Requires 435, found in Storm Peaks and Icecrown
Lichbloom and Icethorn spawns are not really showing up in WoWHead's database yet. I did a fly-by of Stormpeaks and Icethorn and saw both of them in both zones. They're actually in pretty good supply there, unlike some of the lower herbs which seem to have very few spawn locations. Hopefully this list will be helpful to Herbalists/Alchemists out there who are having trouble finding the herbs they need to skill up.
**UPDATE** This information was compiled during the Lich King Beta. For a more current Herbalism list, please go here.