You can learn Outland Mining in Hellfire Peninsula from Hurnak Grimmord (Alliance) at Honor Hold, or Krugosh (Horde) at Thrallmar. You can also learn it from Hanlir at Shattrat City. (or from Fono, if Hanlir is hostile to you)
1 - 75
You can level from 1 to 75 in both of these zones below. Fel Iron will stop giving skill points at around 40, so you will only gain skill points from mining Adamantite Ore after that.
I marked a few caves with a red X on the map. You can usually find one or two Adamantite Deposits in those caves so you should go inside them.
Netherstorm is also an excellent place to level Mining. Just like in Nagrand, I marked two caves with a red X on the map.