There are a couple of ways to approach it.
I park alts at several different trainers around the world:
Ashlei/Alliance Garrison - You can easily use a level 1 pet in Ashlei’s battle and it gives more XP than any other. This is a good place to use pet treats and make sure you are wearing the Safari Hat. You can also hearth back to the garrison to do the daily and maybe the traveling tamer.
Garga/Horde Garrison - same deal, but Garga doesn’t give as much XP.
Vesharr (Veil Terrok) and Tarr the Terrible (Ring of Blood) can also be used to level up a level 1 pet. Taralune (Auchindune) can be used with a level 10 or so pet. Don’t bother with Cymre because that fight is long.
Make sure you pick up the weekly quest in the garrison because you get 10 upgrade stones. The daily traveling tamer gives 3. Those are really useful to top off pets that are 22+.
A good spot to fight wild pets is right behind the Horde Garrison (48,74). There is basically an endless spawn of Icespine Hatchlings.
Tanaan Jungle is ok for pet drops, but the fights are hard and little XP. Worth doing once in a while, but not good for leveling.
These would be Bloodknight Antari (SMV), Major Payne (Icecrown) and Obalis (Uldum). Good XP, fights are not tough and there is a possibility of an upgrade stone. All worth a parked alt.
Lydia Accoste (Deadwind Pass) and Stone Cold Trixxie (Winterspring) are good for the possibility of an upgrade stone, but XP is not great.
Doing the circuit was the old school way of leveling pets. You can do it in about an hour (which is how long pet treats last) and you may get upgrade stones or a pet. If you don’t want to spend that much time, leave someone at the Halfhill farm and fly over to Farmer Nishi.
The Beasts of Fable series is good for a possible pet drop plus a lesser pet treat, but is really time consuming and not much XP.
Crysa (Northern Barrens) is a quick and easy fight. Good XP, possible upgrade stone and unlikely pet drop.
Environeer Bert (Gnomer) is a long boring fight, but you can stick a level 12ish pet in there. Decent XP, possible upgrade stone and pet drop.
I don’t know much about leveling with Legion tamers, but I have read that it’s a decent option.