"I have news from the North, hunter." The questgiver's words perk your ears right up. You've done all the class quests already.
...Haven't you?
"There is a shaman of some renown who wishes to speak with you. Make your way to her cave in Winterspring, overlooking the tunnel to Mount Hyjal."
So you go. You fly through the icy air and trek through the snow, trudging up through a storm and finally finding refuge in the cave. At the back, you find the shaman--staring into a fire and chanting, waving her hands in the smoke.
"I foresaw your arrival, hunter," she says. "I have three questions for you, and these questions will decide your fate--and the fate of another. Please, sit."
You remember another asking you questions--a gnoll, a sage? He'd been grinning at you from the Darkmoon Faire tent, and you were sure he was a quack until he foretold your future correctly.
"To walk in the sunlight, warm and bright, or slip through the midnight trees?" the shaman asks. There is a strange glint in her eyes as you give your answer.
She nods, as if this was what she had expected you to say.
"Would you kill one to save many? Or would you fight, perhaps winning, or perhaps damning you all?" You think about this for a few minutes, and then give her your second answer.
"What matters more: what you see before you, or the spirit and force behind it all?" One last time, you give your answer.
"Then it is settled. There are many creatures which I see in my visions. Many who need help. And there is only time to save one. Your answers have decided for us. I require of you three things, if we are to rescue this creature..."
She hands you a small piece of parchment. On it are several mysterious and impossible tasks.
A fang of Deathwing?!
A pebble from the bottom of the sea?
An everburning branch from the tainted demons at Hyjal?
A feather from a Feralas Hippogryph...
A length of chain fashioned by Ironforge dwarves...
A sedative created by the Undercity's apothecaries...
You do not understand, but you obey. It is weeks before you return, tired but curious. The shaman wastes no time in creating a single poison-tipped arrow with which you are to subdue this creature--and a chain with which you are to lead it back.
The shaman gives you an elixir. You drink this and enter the world of visions--everything is magical and shimmering, and the normal creatures of the world are gone. Your standard companions are left behind. Everything is silent.
Then, before you, a creature appears in a clearing. There are dark figures around it, poking, stabbing, tormenting. The beast catches your eye: it is the most beautiful creature you have ever seen. (Depending on how you answered and what is currently in your stable, the species, model, color & markings will change--but it will be a Legendary-unique skin, perhaps one of dozens.) The beast fights the figures, but it is bound. You pick them off one by one, and the beast turns to you.
* The creature turns to you and threatens, blindly ferocious due to the torment it has endured. *
You fire the sedative.
* The creature collapses before you, fast asleep--for now. *
You attach the chain, and wait. Soon the creature comes to, and the magically-enhanced chain binds it to you--it follows you silently back to the shaman.
The shaman speaks many words of magic over the beast, and soon she pronounces it your new companion. And it is.
It is larger than others of its kind: faster, stronger, and far more striking to the eye. Finally, a unique pet--one that you saved from the brink of destruction. And you know that now, when others look upon the pair of you, they will fear you both--they will sense the power inherent in this amazing beast, and know that only a truly dedicated and fearsome hunter could have returned alive with it by his or her side.
(I'll add an image or two to this later, but here's the general idea: the old idea for a class quest for a legendary pet. Wtb

Edit, for image: