The Darkmoon Faire - a monthly event that lasts for a whole week and hosts a large variety of fun and games - also contains two pet battle dailies.
The fights against Christoph vonFeasel and Jeremy Feasel (who in reality is also the designer at Blizzard responsible for the pet battle systems), can both be used to level a pet very nicely. They also give a satchel which has a chance to contain one of their pets each:
Syd the Squid
The drop chance is rather low but you can also buy them on the AH if you prefer. In any way, I wish you good luck in acquiring them!
Below you will find a list of pets that are suitable to beat both Feasels. You do not necessarily need those pets, but with them you can use the first alternative listed here on every fight:
The list of required pets can sadly not be displayed right now due to updates Blizzard is making on the armory.
A new version of the tables will be added as soon as possible.