Boneshard + Foulfeather + Almost any 25 flying (possibly just another Foulfeather)
Start with Boneshard
Use Blistering Cold + Chop until Boneshard dies
Bring in Foulfeather
Black Claw followed by Flock
You probably just won
Backup pet does backup things
Boneshard+Foulfeather available on the AH for probably less than 2000g
Already Rare, no need to upgrade if you don’t have upgrade stones
Fixed breeds mean you don’t have to fish for specific pet stats
Will detonate every new legendary battle with little effort
They start at level 1, so you’ll need to level or pay more gold for 25s
Sometimes Boneshard takes too long to die, remedied by using Bonestorm in his third ability slot to kill himself.
Pretty much the only legendary fight that’s going to give you trouble is Unit 17 on Mechagon. Everything else should get smushed real good.
If you don’t want to buy a third pet, go to Pandaria and capture an uncommon/rare firefly pet from Jade Forest/Krasarang wilds/Vale of Eternal Blossoms. They start at level 22 and will fulfill the backup role of almost any strategy anyone recommends you: They’re a flying type, and they have Swarm.