Hunters could be propositioned to track down and tame their mount.... they have to for some of the supper rare companions.
Shamans could have an elemental based mount that takes on various forms with regards to either being on the ground or taking flight in the air.
Warriors being the embodiment of tanking and durability, who can take a beating and survive could receive a mount that is as durable and tough as they are.
The magi could be given something conjured out of the ether.... similar to the way they conjure their water elemental, bringing it into existence.
As for a Priest...now that is a difficult one. It would have to be a mount that personified the priests' essence for protection and giving of life.
Rogues' could get a creature such as...reaching back into D&D knowledge here, a displacer beast or some other animal which through the use of poisons and stealth takes down their prey.
Now for monks.... I would like to see them have a mount which embodies their tranquil yet combat competent nature... not to mention their love of good food, good drink and friends.
I know this is a tall order which may seem completely out of the mainstream, but it seems to me as though we (the players) are intentionally losing what makes our class unique. Yes, yes we all fall into categories of (Tank, Melee DPS, Ranged DPS, and Heals) but were does our uniqueness come in, why must we be so homogenized. I feel that characters ought show their sense of uniqueness not only in their game play but in the way they explore the environment as well.
P.S. Now that the short comment has been made long...... thank you for a great game. I have really enjoyed Pandaria and can't wait for the up and coming 5.2 patch.... Dino riders here we come.... I know, lame, but hey that is okay. The point is to have fun in life, don't stress over trying to fit into the norm, being yourself is the best way to be.