Outland Herbalism Trainers
You can learn Outland Herbalism from one of these trainers below:
1 - 50
If you have the [Sky Golem] mount, you should use it while leveling herbalism because you can pick herbs without dismounting.
You can actually level all the way up to level 75 in these zones, but I recommend switching to Netherstorm or Shadowmoon Valley at around 50-55 because you will start getting skill points a lot less frequently from Felweed and Dreaming Glory. Netherbloom in Netherstorm and Nightmare Vine in Shadowmoon Valley will be orange until 75, so you will get skill points every time you find one of those herbs.
Blade's Edge Mountains
50 - 75