Emperor crab with p/p breed is a really strong pet, really beats up on critters and elementals, and can take down almost anything else that isnt a flier aswell without much trouble :)
As said above, Anubisath Idol and p/p emerald proto-drake are two of the easiest pets to defeat trainers with, the emerald drake is pretty much impossible to kill if you are careful with it.
A rabbit is really good vs pandaren earth spirit who can be a bit of a pain otherwise, and im sure there is other place where they can be effective, with 2 abilities that can make them dodge attacks.
I would also recomment a moth pet aswell, they hit hard and their cocoon strike is a really strong ability, p/p yellow moth is the best in most cases, but it can be a little tricky to get, but really any rare moth should do fine :)
A p/p nexus whelpling is really nice vs flying pets, it can 2 shot most of them with its mana surge.
Chrominius is a strong pet you can easily pick up from the ah, with 2 healing abilities its hard to heal, and its howl can be used together with pandaren water spirit to cheese out some of the beasts of fable that can otherwise cause trouble
There is probaly some i forget, but this is some of the pets i use the most vs the trainers of pandaria :)