So far all suggestions actually really suck. They are either too slow, or outdated..
Let's start with the answer to the ultimate question: Can you buy level 25 pets? Yes you can. I sell them all the time...
The fine print however: You cannot add any pet to your list that's of a higher level than your highest level pet. So, there's no short cut by buying a 25 pet, if you don't have one already...
For a starter player there is no such thing as a fastest way. It's a grind at the start...
The most efficient way however is, to follow the quest chain, that's given to you by the pet battle trainer in your capital city..
Adding to the speed is, to have 2 toons - one from each faction - that are capable to travel efficiently in both vanilla continents.
And then, here's what you do:
Battle Tamers of Eastern Kingdom: Do this quest with your Alliance toon.
There are more tamers in both continents, than the quest requires. Fight them all..
Here's a link with coordinates in the comments section.. you essentially start outside Stormwind, then work your way along the tamers and their pets respective levels.
For the very last tamer wait... For EK this tamer sits behind the Kara instance, you can't miss her. Leave her out for now...
Switch to your Horde toon and do the same thing again, but this time you take on the tamers of Kalimdor.
Again, link with coords... you start just outside Orgrimmar, and again follow the tamers by their pets levels.
For the quest that wants you to fight the tamers on each continent, that gives you a one time only opportunity.... You can fight them twice back to back.
If you've done all of these battles, and use decent pets for your first team of 3 pets, you should have 3 decent pets that are capable to beat both final tamers, the one in EK behind Kara, and the Kalimdor one in Winterspring.
What pets to pick for the first team?
1... Anubisath Idol
2... Lil XT (if you got one), otherwise go with a moth.
3... Any rabbit..
After that mission, you got Outland unlocked. Try battle those tamers, and as you progress, try capturing pets of higher levels. If you got track battle pets active at your tracking UI, the map displays the battle pet levels for each zone.
Once you've gone through all the chains and are finally in Pandaria, fighting the tamers, spirits and beasts there... Leveling a pet from level 1 - 25 takes about 30 minutes... not more anymore. By then you'll have a hat that gives 10% XP gain for the pets... The beast dailies give a pet treat that grants another 25% gain.
And if you happen to be good enough with a set of pets to win 10 level 25 pvp battles, you get another guaranteed treat that grants 50% XP... All XP gains stack with each other.
I usually do one cycle in Pandaria, doing all beasts, spirits and conventional tamers, and that gives me 2 pets to level 25. I don't use level 1 pets for this task. I level them on the lowbie tamers to level 5 - 10, because anything lower than level 10 translates into an XP loss in Pandaria..
"The pen is mightier than the sword.. and considerably easier to write with."
you can buy a lvl 25 pet but if i remember correctly u have to have at least 1 pet on lvl 25 to use it