Alas, my 85 hunter already has Sambas, Rak, the hunched tiger and Sian. couldn't bring myself to get another cat on her.
So I rolled a new toon, specifically to get this pretty:

And a few others that I really liked.
And of course I made her a Horde for some odd reason!
Corpse running into that place at level 16 is.... very, very, VERY hard. Spent about an hour and a half last night with no luck, kept getting one shotted before I could get close or use my rocket boots.
Took about an hour and a level 65 Paladin from the guild who was bored enough to help me out but we eventually made it in. I snuck up behind the portal and tried to sneak up, but I was one shotted. He rezzed me popped a bubble around me and I was in the pink void of voidiness! Landed in Darnassus and wow all my night elf friends, who salute when my Worgen goes running by, killed me... AGAIN!
But I took a rez sickness in the island-thwarting their attempts to stop me. My Pally bud flew himself in after I got there, and I ran to where my pretty was waiting-as I already knew where he was because I took my other hunter out there and sat with him.

Here he is, my pretty pretty kitty with my teeny, tiny goblin.

So it is possible for a lowbie Horde to get to him-though it was bloody difficult.
Now this has been one of the hardest to get to tames I've done in awhile. Going to have to think up an epic name for this pretty.