I am thinking perhaps one of the pets that are not available as rares.
Green quality pets with unique abilities:
- Mechanical Pandaren Dragonling
- Jade Crane Chick
- Gilnean Raven
- Creepy Crate
- Feline Familiar
- Legs
- Magic Lamp
- Tiny Flamefly
- Personal World Destroyer
- Warbot
- Curious Wolvar Pup
- Curious Oracle Hatchling
- Mechanopeep
- Enchanted Broom
- Proto-Drake Whelp
- Ghostly Skull(#7)
- Willy
- Wolpertinger
- Peddlefeet
- Tiny Snowman
- Tranquil Mechanical Yeti
- Lifelike Toad
- Pet Bombling
- Mechanical Squirrel
- Winter's Little Helper / Father Winter's Helper
..or one of those pets who are obtainable as rares, but have loads of different breed IDs AND are overcamped, so it might just be easier to upgrade an uncommon one.
- Nether Faerie Dragon(#4)
- Wildhammer Gryphon Hatchling(#4)
- Nordrassil Wisp(#5)
- Flayer Youngling(#5) - I got this as rare now, so I won't be using my stone on this one atleast

- Molten Hatchling(#18)
..or Red Cricket because of its awesome power, and I only got a poor quality from Sho my best friend.
..or Yellow Moth(#4) with loads of power.
As you can see, I am torn.
The idea of 3 rare Creepy Crates picking on the weakest in the group is tempting, and with them beeing undead, a finishing BONESTORM x3 seems very nice.

A rare Tranquil Mechanical Yeti would be the only mechanical with the ability to Call Lightning, together with a rare Personal World Destroyer's supercharged Quake, and we're talking nice aoe damage. Extra damage per attack paired with Clockwork Gnome's Build Turret, or a rare Pet Bombling's Batter or a Lifelike Toad's Tongue Lash or a Mechanical Squirrel's Trash. There are just so many possibilities opening up in the mechanical world with the stones!

Gilnean Raven with Call Darkness + Nocturnal Strike, but then again perhaps Nevermore (Your opponent's next ability becomes unusable for 5 turns) is better.
Legs had a nice burst combo: Whirlpool + Pump(first use) + Pump(second use) + Whirlpool deals its damage and you also use Surge of Power. If you do all this during Cleansing Rain, thats another 25% dmg.
Magic Lamp with the typical Magical Crawdad spell called Wish, and another spelled named Sear Magic(Removes all buffs and debuffs) could come in handy, but those spells aren't really that dependant on pet quality.
Curious Oracle Hatchling's Aged Yolk(Removes all buffs and debuffs) is the same as Sear Magic, and since it has low speed, it doesnt really have that much more going for it.
Curious Wolvar Pup's aoe Whirlwind has quite a punch, but it also has a 3 round CD.
Enchanted Broom, now this is a nice one! Batter will most likely cause an extra attack because of its high speed. Sweep will remove an enemy pet from the battle for 2 rounds, a very nice ability! And it also has the Wind-up ability that can be prepared before you use sweep to make sure you don't use it on an opponent it's weak against.
Ghostly Skull, well, it's an undead, so thats a big plus. It has two heals, so it could potentially stay alive a while(aim for the breed ID with high power to get better heals). And then you have the tier 3 abilities, both potentially good, but I would go for Ghostly Bite since stuns are really nice in PvP. Unholy Ascension would only be used as the last spell you use as immortally resurrected for 1 round, I would much rather go for a stun every 3 rounds.
Willy.. he could be good, could be bad. It kind of depends on what spells you get with Dark Simulacrum. It does have Interrupting Gaze, the ability to interrupt multi-round casts, on a 3 round CD, so it could gimp many heavy hitters. Worth keeping an eye on, so to speak.

Peddlefeet, I do like his aoe and selfheal ability and a 25% chance to stun every 3rd round. Interresting.
Tiny Snowman, 3x elemental damage spells, which hits mechanicals for loads, and mechanicals are often seen in PvP. 2 round root on a 3 round CD, and a 3 round CD stun.
Winter's Little Helper's Gift of Winter's Veil is a nice startup to chop away 25-40% of the enemy hp instantly, then Call Blizzard and spam Ice Lance until Gift of Winter's Veil is ready again.
So I guess
Tranquil Mechanical Yeti (mechanical) / Personal World Destroyer (mechanical) /
Enchanted Broom (magic) / Legs (magic) /
Ghostly Skull (undead) / Creepy Crate (undead) /
Winter's Little Helper (humanoid) / Peddlefeet (humanoid) /
Tiny Snowman (elemental) /
Red Cricket (Critter) are my top choices.