The most effective way to level up pets (apart from using Training Stones) is fighting against trainers. The majority of those encounters grant 5x more experience than defeating wild pets.
Unfortunately a lot of those are limited to just one fight a day. Therefor we need trainers which we can challenge repeatedly to use them for 'powerleveling'.

I want to list these here and also provide you with tips for this powerleveling.

1. Repeatable Trainers

1.1 Squirt

Since she is the most famous and best tamer for powerleveling she deserves her own topic. There are strategies enabling you do beat her in 80 seconds. On top of that right next to her is a NPC that can heal your pets after every fight for free. Unfortunately Squirt no longer grants experience to the player's character.

You can find her every 15 days in the menagerie of your garrison. A level 1 menagerie will do (level 2 to unlock the free healing) but this requires a level 3 garrison beforehand. Building the menagerie will also reward you with a Ultimate Battle-Training Stone which can upgrade one pet directly to level 25.

Squirt dates in 2019:
Recommended strategy:
Bronze Whelpling + Widget the Departed
Fight duration: ~1:20
Fast, reliable and safe for level 1 pets.

1.2 Tamers from Legion

Some of the tamers from Legion (almost all of which you need for 'Family Familiar') can also be challanged multiple times.
It's worth looking out for their active world quests because only then they are available for fighting.
Unfortunately their appearence is decided randomly, so you can't plan ahead when to challenge them.

Since those tamers don't stand right next to a stablemaster you should bring enough Battle Pet Bandages with you.
But in return defeating these trainers also grants your character experience and that's why especially the short fights have become a popular method for leveling.
Using heirloom gear and activating warmode you can get (depending on your level, you can do this as early as level 1) as much experience doing this as you would from finishing a quest.

Here follows a list of the respective tamers, together with a recommended strategy and sorted by their effectiveness in powerleveling:

Odrogg
World quest: Snail Fight!
Location: Highmountain
Recommended strategy:
Teroclaw Hatchling
Fight duration: ~1:45
or
Xu-Fu, Cub of Xuen
Kampfdauer: ~1:35
Reliable and safe for level 1 pets
Doesn't need a bandage after every battle!


Sir Galveston
World quest: Fight Night: Sir Galveston
Location: Dalaran
Recommended strategy:
Court Scribe + Surger
Fight duration: ~1:10
Fast, reliable and safe for level 1 pets


Robert Craig
World quest: My Beast's Bidding
Location: Stormheim
Recommended strategy:
Ranishu Runt + Menagerie Custodian
Fight duration: ~1:15
Fast, reliable and safe for level 1 pets


Bodhi Sunwayver
World quest: Fight Night: Bodhi Sunwayver
Location: Dalaran
Recommended strategy:
Void Jelly + Wicker Pup
Fight duration: ~1:30
Fast, reliable and safe for level 1 pets


Tiffany Nelson
World quest: Fight Night: Tiffany Nelson
Location: Dalaran
Recommended strategy:
Darkmoon Zeppelin + Nexus Whelpling
Fight duration:
Fast, reliable and safe for level 1 pets


Amalia
World quest: Fight Night: Amalia
Location: Dalaran
Recommended strategy:
Iron Starlette + Spawn of G'nathus
Fight duration: ~1:40
Reliable and safe for level 1 pets


Xorvasc
World quest: Dealing with Satyrs
Location: Val'sharah
Recommended strategy:
Mechanical Pandaren Dragonling + Fossilized Hatchling
Fight duration: ~1:40
Reliable and safe for level 1 pets


Grixis Tinypop
World quest: Tiny Poacher, Tiny Animals
Location: Highmountain
Recommended strategy:
Direbeak Hatchling + Darkmoon Zeppeling
Fight duration: ~1:45
Reliable and safe for level 1 pets


Trapper Jarrun
World quest: Jarrun's Ladder
Location: Stormheim
Recommended strategy:
Iron Starlette + Darkmoon Zeppeling
Fight duration: ~1:50
Reliable and safe for level 1 pets


Andurs
World quest: Beasts of Burden
Location: Stormheim
Recommended strategy:
Iron Starlette
Fight duration: ~0:40
Note: Only repeatable if you fight just Andurs and not Rydar. Once you've completed this world quest you can't challenge him again.
You get less experience from him then you would get from the other tamers listed here. In return this strategy is reliable and really fast.
Since this is a short fight you'll need more bandages (or more Iron Starlettes) but you can also gain the character experience faster.


Aulier
World quest: The Master of Pets
Location: Suramar
Recommended strategy:
Mechanical Axebeak + Sprite Darter Hatchling
Fight duration: ~2:00
Requires a certain story progress in Suramar
Reliable and safe for level 1 pets


Varenne
World quest: Chopped
Location: Suramar
Recommended strategy:
Crispin + Direbeak Hatchling
Fight duration:
Requires a certain story progress in Suramar
Safe for level 1 pets


Nightwatcher Merayl
World quest: Training with the Nightwatchers
Location: Azsuna
Recommended strategy:
Nexus Whelpling + Chrominius
Fight duration: ~1:30
Fast and reliable, but the level pet has to be at least level ~12


Bredda Tenderhide
World quest: Training with Bredda
Location: Highmountain
Recommended strategy:
Rebuilt Mechanical Spider + Twilight Clitch-Sister
Fight duration: ~2:20
Long fight with a rare chance of failing, but safe for level 1 pets

2. Other possibilities

All the tamers listed have to be active to be usable for leveling the whole day. So what alternatives are there for days on which they aren't avalable?

2.1 Noteworthy Tamers

As described at the beginning these trainers grant a lot more experience than wild pets.
Therefor it is worthwile to fight those who also give 5x the experience (just like Squirt), even though they are opposable just once the day.
Admittedly you have to count in a considerable time for traveling. On the other hand you can get, besides the experience obviously, other useful rewards (even pets) and the daily quests grant a lot of experience to your character. Especially the daily routes through Pandaria and Draenor are popular for this reason. Often times characters are parked at Crysa and Environeer Bert or even at the Darkmoon Faire whenever it is active.


Warlords of Draenor Daily Quests

* Ashlei (even 6x the experience)
* Gargra
* Cymre Brightblade
* Taralune
* Vesharr
* Tarr the Terrible
⇨ Bigger Map






Mists of Pandaria Daily Quests

* Hyuna of the Shrines
* Farmer Nishi
* Mo'ruk
* Courageous Yon
* Seeker Zusshi
* Wastewalker Shu
* Aki the Chosen
* Whispering Pandaren Spirit
* Thundering Pandaren Spirit
* Burning Pandaren Spirit
* Flowing Pandaren Spirit
⇨ Bigger Map


Darkmoon Faire Daily Quests

* Jeremy Feasel
* Christoph von Feasel


Eastern Kingdoms and Kalimdor daily quests

* Crysa
* Environeer Bert


Other Legion Fights (not repeatable, also require world quest)

* Beguiling Orb
World quest: Dazed and Confused and Adorable
Location: Azsuna
* Fragment of Fire
World quest: Only Pets Can Prevent Forest Fires
Location: Val'sharah
* Ominitron Defense System
World quest: Oh, Ominitron
Location: Stormheim
* Durian Strongfruit
World quest: Training with Durian
Location: Val'sharah
* Felsoul Seer
World quest: Threads of Fate
Location: Suramar
* Surging Mana Crystal
World quest: Mana Tap
Location: Suramar
* Ancient Catacomb Eggs
World quest: Clear the Catacombs
Location: Suramar
* Sissix
World quest: Illidari Masters: Sissix
Location: The Broken Shore
* Madam Viciosa
World quest: Illidari Masters: Madam Viciosa
Location: The Broken Shore
* Nameless Mystic
World quest: Illidari Masters: Nameless Mystic
Location: The Broken Shore

2.2 Wild Pets

Of course you could go to all the remaining tamers, but because of the ever decreasing experience you'll reach a point at which the time for traveling isn't worth the rewards (even character experience and other stuff) anymore. Also these remaining ones are fightable only once a day aswell.
If you are still looking for a unrestricted way of leveling your pets there is only the option of fighting wild pets left.

In this situation it is clever to find a location in which are as many predictable pets of one family as possible so it becomes easy to create a team that can counter these pets the best.

Fastest Option in the Wilderness

The fastest alternative is fighting Icespine Hatchlings in Frostfire Ridge.
With the following team you'll need just 30-60 seconds for one fight and your pets will barely lose health so they can used more often before needing to be healed.

*Rotten Little Helper (1,1,1)
*Feline Familiar(1,1,1)
*Level pet (should have 300-500 health)

vs. Icespine Hatchling
-Booby-Trapped Presents
-Greench's Gift
-Club until enemy dies
vs. 2nd enemy
-Club until enemy dies
vs. 3rd enemy
-swap to level pet
-swap to Widget the Departed
-Stoneskin
-Onyx Bite until the enemy can be killed with Devour


Other noteworthy Locations and Pets

* Dancing Water Skimmer in Vale of Eternal Blossoms (~80% aquatics and ~20% fliers)
* Icespine Hatchling in Frostfire Ridge (~50% beasts, ~25% critters and ~25% fliers)
* Moonshell Crab in Shadowmoon Valley (Draenor) (~50% aquatics, ~30% fliers and 20% beasts)
* Critters in the Valley of the Four Winds (80% critters and 20% aquatics)
Especially the Marsh Fiddlers there are good for leveling level 1 pets since there is just a small chance for them dealing damage in the first turn.
* Dragonbone Hatchling in Dragonblight (~40% fliers, 30% critters and 30% aquatics)
Appropriate for leveling for the same reason. There also is a stablemaster nearby (at the temple) who makes the leveling more enjoyable.


Of course you can look for good locations yourselve. It's all a matter of having the right pets to counter the wild ones.
As an example for fighting aquatic pets both Golden Dawnfeather and Pterrordax Hatchling are suitable and against critters every cat with Devour will do great.
The Feline Familiar is even effective against fliers and critters, has a strong protection and also a healing ability (Devour), which is the reason why it is popular for leveling in the wilderness.

3. Tips, tricks and hints

3.1 Increasing the Experience

Although most tamers already grant a lot of experience it can be useful to increase that even more. All of the following increases can stack:

Experience Increases

*Safari Hat: 10% more experience.
It's a toy that can be used without cooldown. You get it as a reward for the achievement Taming the World.
*Lesser Pet Treat: 25% more experience for one hour.
Used on a pet as a target, but acts as a buff on you. Available at multiple pet vendors for 5 Polished Pet Charms.
*Pet Treat: 50% more experience for one hour.
Used on a pet as a target, but acts as a buff on you. Available at multiple pet vendors for 10 Polished Pet Charms.
*Darkmoon Top Hat: 10% more experience for one hour.
You can buy it from Gelvas Grimegate for 10 Prize Tickets while the Darkmoon Faire is active. The buff can run out while your character is logget out and it will also disappear when the Faire isn't active anymore.


During the time of the Pet Battle Bonus Event you get a buff for 200% more pet experience! Look out for in in your calandar and prepare your teams.

Dates for the Pet Battle Bonus Event in 2019

*May, 22nd - May, 28th
*July, 10th - July, 16th
*August, 28th - September, 4th
*October, 16th - October, 23rd
*December, 4th - December, 11th

3.2 Required Amount of Fights

Depending on the active experience increases you'll need a different amount of fights to level a pet from level 1 to 25.

This list applies for every tamer which gives 5x experience:

Without any increases:
1st fight: 10
2nd fight: 15
3rd fight: 18
4th fight: 21
5th fight: 23
6th fight: 24
7th fight: 25

With the Safari Hat:
1st fight: 11
2nd fight: 16
3rd fight: 19
4th fight: 22
5th fight: 23
6th fight: 25

With the Safari Hat and both Treats:
1st fight: 14
2nd fight: 20
3rd fight: 24
4th fight: 25

During the Pet Battle Bonus Event, without any further increases:
1st fight: 17
2nd fight: 24
3rd fight: 25

During the Pet Battle Bonus Event, with the Safari Hat:
1st fight: 17
2nd fight: 25

During the Pet Battle Bonus Event, with the Safari Hat and both Treats:
1st fight: 19
2nd fight: 25

3.3 Rematch and TD-Script

Especially in a powerleveling session when you are constantly repeating the same fights it is recommended to use Rematch and TD-Scripts. With those it is possible to execute an entire pet battle just by pressing one button.

Guide: Using Rematch + TD-Script

Good Luck!