Rexxar wanders the road from Feralas to Stonetalon Peak, except he cuts north from the area with the demons and goes through the Kodo Graveyard, before taking the road north out of there (or south into there). He also wanders slightly into Stonetalon Peak and Feralas (as far as The Twin Colossals in Feralas) so if you're having no luck finding him, search a little into both zones.
Rexxar, one of my most loyal champions, has discovered a way into the lair of the dragon. However he has left Azeroth to join our expedition into Outland.
However, he left his companion, Rokaro, in Shadowprey Village with this information. You are to seek him out.
Progress
Keep at it, <name>.
Completion (Pre-Burning Crusade)
There is but one way into the dragon's lair, <race>.
You see, only the strongest of the Black Dragonflight are allowed entry into the lair of the brood mother. Many trials must be passed and the key to enter ceremoniously enchanted by General Drakkisath himself!
Since you are not of black dragonkin, you may have some difficulty in obtaining passage.
<Rexxar grins.>
Completion (Post-Burning Crusade)
There's only one way you'll be getting into the dragon's lair. Unless, of course, you happen to be an honored member of the Black Dragonflight.
Even then, you'd have to pass many trials and then have the key enchanted by General Drakkisath himself.