I have a whole series on this in the Pet Battles forum. I’ll put them at the bottom in case you’re interested, but you don’t have to go through it all.
One Level 25 Grumpy will take care of most of what you need!
Either Grumpy or Lord Woofington
These two have the combination Howl → Superbark. Using that does a huge amount of damage, BUT CANNOT KILL the target. This is your ideal capturing mechanism for the pet you want to tame.
Set Grumpy up. Use Howl, then Superbark on the pet you want to tame. Then keep throwing the trap until you have captured it. Then just Bark with Grumpy until you have killed the other two. Simples.
For higher level captures, Grumpy would appreciate two solid, Tanky pets to back him up and finish off the rest of the opposition.
Now let’s look at the cats you identified.
Cat: tamed in Ellwyn Forest, these Cats will be about level 3-6. You can tame them easily with a team of level 8 pets, but a Level 25 Grumpy will be plenty.
Cheetah Cub: tamed in Northern Barrens, it will be level 5-7, or lower. As with the Cat, your Level 25 Grumpy will happily clean up the whole opposing team easily.
Fluxfire Feline: From Gnomeregan/Dun Morogh, these are like level 3 IIRC. Again, Grumpy will make short work of the whole opposing team.
Snow Cub: Same as Fluxfire.
Sand Kitten: From Tanaris. Tanaris pets will be Level 14-15ish. While your 25 Grumpy probably could manage these on his own, this is where he might appreciate some backup. This is where your two other tanky pets come in.
My ideal tanky pets are Anubisath Idol or Void-Scarred Anubisath; P/P breed Emerald Proto-Whelp; P/P breed Emperor Crab. The latter two are high-level tames.
You could buy an Anubisath and throw an Ultimate stone on it, but that might cost a few thousand. I see you have a Lil’ Bling. At level 25, with Inflation, Extra Plating, and Make it Rain, he will be more than plenty for some Level 14s. Use Make It Rain, then Extra Plating, then Inflation, in that order.
Anything else you want to know, or any help you need, just ask!
Appendix:
From your armoury, you have a Level 70, and I’m guessing you have finished the Campaign and opened World Quests.
You ought to have a quest in the Little Scales Daycare in Valdrakken (sort of hanging off the right side when you come out of Seat; it’s on your map)
This starts a short sequence of quests that reward you with three pets and two Ultimate Battle-Training Stones. You can use the Stones on the pets you get, but you don’t have to; you can use them on others.
Oh. I see you started that, but never got the Shyfly.
Anyway, that chain might be something you look at later.