Wall of text for strategy details, tips, and tricks. Don't freak out. The reading is long, the method is fast. TL;DR below.
For this revised strategy, I'm going to assume a high-level character that *just* learned pet battles and has zero acquired pets beyond what companions you accumulated pre-MoP. IMO, this is the fastest way to get max level pets and subsequently a very efficient way to get all of your pets to level 25. I call this method the "fast but hard" way to 25. "Fast" because you spend virtually no time grinding pet levels, but "hard" because your battles along the way can be challenging and you will lose sometimes. Once you have a small team of level 25 pets, it becomes very easy to level new ones quickly.
This strategy should include virtually no level "grinding" with an exception I'll mention below. I'm going to assume you've read a guide on the basics of pet battling and that you will use this website to look up what zones have what level pets. I also highly
recommend the addons Pet Journal Enhanced and Battle Pet - Quality Notifier.
The core of the "fast" strategy is "leap-frogging" your captures to get higher and higher level pets. Take your first pet(s) to a zone that has pets 1 or 2 levels higher than those in your team. Challenge those pets and capture them. Once you've got a team of level 10 pets, you should be able to have 3 pets in your team. Get any 3 different pets of the level in the zone you're in then take that new team to the next zone level up and repeat the process. Continue this leap-frogging by constantly swapping out your team for the highest level pets you've captured. You'll notice the "hard" part comes in because you are constantly at a level disadvantage to the wild pets, which will result in some lost battles along the way. Protip 1: I highly recommend capturing or acquiring at least one pet of every family as you go. (Protip 2: If you're in a battle with a pet that you really want to capture, but your team is getting owned, log out from inside the battle. When you log back in, the pet you were after will still be there for the taking, rather than despawning after a failed fight.)
After a while zipping around "leap-frogging", you'll end up in Pandaria with a full team of level 22-23 pets. Tada! "But wait," you say, "I wanted level 25 pets. What gives?"
The highest level pet you can ever have after a capture is 23 (but finding level 25 wild pets in Pandaria requires hunting, so most likely you'll have a level 22 team unless you're just stubborn like that). This is the exception to the "no level grinding" I mentioned before. You simply have to suck it up and level a few pets from 22 to 25. Boo. BUT! Here's the second part of the strategy to the rescue!
I highly recommend picking up a rare Amethyst Spiderling
(AS) from Krasarang Wilds and a rare Sandy Petrel
(SP) from the Windward Isle in Jade Forest (or as a secondary in the Arboretum if you can't fly in Pandaland yet). Also, pick up an extra of either pet, but don't sweat getting two rares. If you just can't find a rare, uncommons should be fine.
Take your team out to Halfhill in Valley of the Four Winds and get comfy. Why? The Stable Master there is surrounded by battle pets that often come in groups and they are very easy to get to and back from. Also, in that area there are only two types of wild pets, Critter and Aquatic. This means every fight is stacked with either all Critter, all Aquatic, or a mix of the two. Notice I recommended a Beast type and a Flying type? I chose those two pets because you can set them up so every one of their abilities deals their specific family damage type, which is very strong against what you'll be fighting. For the Spiderling, use Strike, Brittle Webbing, and Spiderling Swarm. For the Petrel, use Slicing Wind, Cyclone, and Lift-Off. This combination will chew through wild pets in a hurry. In fact, plenty of times I've opened with Brittle Webbing followed by Spiderling Swarm and the Critter is dead in two turns. I've seen critical Lift-Offs one-shot Aquatics. It's a very strong composition for the area.
So now you have a small team of level 25 pets about as fast as it can be done. Success! What about amassing that army? And "Hey, what about the battle pet trainers? I haven't fought a single one and I heard they grant bonus xp." You're right, and for amassing an army, you'll absolutely want the Safari Hat
from the Taming the World
achievement so taking down trainers is important, but
I don't recommend using trainers to level pets because you can only get that bonus xp once a day and that's a lot of travel time you could be using to fight more wild pets. I do recommend getting one of each pet family (preferably with three abilities specific to its family type) before taking on the trainers because a level 25 team dealing strong damage will plow through trainers so fast the slowest part of the process will be getting to them. To max out one of each family, just stay right there in Halfhill and use the following method.
Put the pet you want to level in your first slot, followed by the AS and SP. Start a wild battle. Use your lowbie pet to cast any ability. It may miss and your pet will probably take a hit, but not die. Rotate the pet out to either the AS or SP based on whether the wild team is predominantly Critter or Aquatic and finish them off. Your lowbie pet gets a huge xp bonus. Ding! Rinse and repeat.
Something to keep in mind is that the xp from a fight is "divided up" among all the surviving pets that actively participated in the battle, even if the pet is maxed. XP divided to a max level pet just goes to waste so every battle, use the least number of pets you can. Don't be afraid to let one of your maxed pets die and finish the fight with the other one. This way the xp is still only divided among two pets. Even better, as your lowbie pet gets closer in level to what you're fighting, get the wild team down to just a small hit or two on its final pet and let it kill your maxed pet. Bring in your lowbie and have it finish the fight. Booyah, even bigger bonus xp! Huge, in fact. Keep in mind you don't have to waste time bringing in your third pet just to let it die. The xp bonus works even like this: Pet 1 starts fight and rotates out, Pet 2 kills all pets except last one, Pet 2 dies, Pet 1 finishes fight, Pet 3 lives but was never brought out. Pet 1 still gets
100% of the xp as if Pet 3 wasn't even there. Awesome!
This gets you one of each family to 25 pretty fast. Go plow through the trainers for that Safari Hat and once you've got it, throw that baby on and head back to Halfhill. Repeat the earlier leveling method and you'll blow through Pro Pet Mob in no time! Keep on going and you'll find yourself ranked among the top trainers on your server.
Have fun! Once you've got lots of pet types up to 25, you may get sick of Halfhill and want to venture off and find another spot to set up camp. Just look for a spot near a Stable Master that has lots of wild pets around whose types are limited to two (so you will always be doing strong damage). I like Halfhill because of what I said before, but also because it's easy to get to from the Alliance capital in Vale of Eternal Blossoms, it's right by Silken Fields so I can take my daily crack at an Imperial Moth
and I can hit up several trainer dailies without going too much out of the way. Plus, Halfhill is pretty. TL;DR - Fastest way to tons of level 25 pets from nothing:
leap-frog pet levels by capturing, "grind" up an Amethyst Spiderling
and Sandy Petrel
from 22 to 25 near Halfhill, use them to level one of each family to 25, beat all the trainers for the Safari Hat, go back to Halfhill with your AS and SP and power level pets up to 25 to your heart's content. Collect Singing Cricket