Meep's guide to pretty cool commons 
Remember, these are all out of my heart, if you want one up in this guide, feel free to post after I reserve a few spaces (:
Cats:
Black non-saber cat. Most found in Stranglethorn, but if you are leveling a goblin, you can tame one starting at level 10. They're easy to find, and the lowest level you can tame one is at level 24-25 (waiting for confirmation that they spawn at level 24, but positive that they spawn at level 25) No rare mob for this skin.
Black spotted non-saber cat. Found in Kalimdor, most found in Teldrassil. If you are a alliance hunter, you can tame one after you learn "tame beast". Horde hunters, you have two options to tame, either go through Stormwind, get onto the boat to Kalimdor, run all the way up (or spirit rez) to the Darnassus, and run like there is no tomorrow through Darnassus, and then tame. The second option is to wait untill level 23-24 to tame one of these in Stonetalon. They also spawn in the CoT dungeon, Opening of the dark portal (That one, I assume) which are tameable starting at 67-68. No rare for this skin.
Lower Versions are found in Mulgore and Northern Barrens. Horde can tame these either starting after you learn tame beast, or reach level 11. Alliance will have to take a long walk to Northern Barrens to tame one, but it is possible (I DID as a level 40 noob go all the way out to eversong to tame a lynx). They can also be found in CoT old hillsbrad foothills, and Hillsbrad Foothills, and along at 85 in H-Z/A. There is one rare for this skin, and that is Broken Tooth.
Red Tigerskin non-saber. Most found in Stranglethorn, tameable starting at level 24. Killed for the Nessingway quests.
Dark Tigerskin non-saber. All found within Darkshore, Teldrassil, and Azuremist Island. Same with the Black Spotted cat for the horde and alliance. No rare for this skin.
There will be more cats added in time
Bats:
Brown Bat skin. Found in trisfal glades and ghostlands. Tameable for horde after learned "tame beast", and for alliance you would have to take a long walk out to Ghostlands and Trisfal Glades. No rare for this skin.
Red Bat skin. Lowest mob found in Trisfal Glades. Same reasoning for alliance who want to tame him as Brown Bat skin...a really long walk.
Tan bat skin. Tameable for both fractions at level 26 in the instance Razorfen Kraul. They area elites, and the group might kill them, but if the group is nice, they will probably allow you to tame one. No rare for this skin, but a lot of elite mobs.
White Bat skin. Tameable at level 9 in which the mob is a rare. The second lowest mob is a semi-rare, and is related to the Aeonaxx spawn. It only stays spawned for about 6-7 seconds, and has NOT been killed yet. (Working on that as soon as I start camping Aeonaxx). There are three rares for this skin, and has the same thing as the Red and Brown skin with going out to Trisfal for the lowest spawn.
Tallstriders:
Brown Tallstrider Skin. Tameable to both horde and alliance hunters after learning "tame beast". Alliance is located on Azuremist Island, horde in mulgore. No rare for this skin.
Tameable for horde starting after you learn "tame beast". Grey Tallstrider Skin. Alliance after you hit 16-17, you can head up to Northern Barrens for one. No rare for this skin. 
Pink Tallstrider skin. Tameable for horde after learning "tame beast". The lowest mob is a rare, and asides in Mulgore, so it will be pretty hard for alliance to get in. The next one that you can tame is at 31-32, and in Southern Barrens (you may remember them from the 'fire' pet) Rare for this skin, the world famous Mazzranache.
Purple Tallstrider Skin. Tauren starter pet, and tameable for hunters at level 70. This mob is located at the rogue island in Terokkar Forest. No rare for this skin.
Tameable for the alliance and horde starting at level 14. Blue Tallstrider Skin. The lowest mob for this skin is a rare, and located in Darkshore. The next available to tame is level 52, and located at the swamp of sorrows. One rare for this mob.
White Tallstrider Skin. Available to tame at level 10 after learned "tame beast". The next available to tame is at Northern Barrens, and ranges in level 11-12.
This is all I could stand to do for the moment. More will be added soon (:
