Not the easiest place for Alliance to get to, but...
From Auberdine, you'd need to head through Ashenvale, until near the east side, head down into the Barrens, go all the way down the Barrens into Thousand Needles, go down the southeast path of Thousand Needles, and all the way down the salt flats of the Thousand Needles, and then you're in Tanaris. Gadgetzan is right there.
Alternatively, you can skip Ashenvale if you have a flightpath to Ratchet.
Also alternatively, you can go through Stonetalon Mountains, through the Charred Vale into Desolace, go all the way down Desolace into Feralas, all the way through Feralas, south and then east, and then through Thousand Needles...
Honestly, the Barrens/1kNeedles path is the best way to go. It's all Horde questing area though, so be cautious. I don't feel bad for you since we Horde have to go through Wetlands/Dun Morogh/Loch Modan to get to the Badlands
.