These (and most other rare "area spawn" pets) are rather easy to find using the server-hop feature.
1) Fly out to the area where the pet is "supposed to be".
2) Open the 'Looking for Group' tool.
3) Select 'Premade Groups'.
4) Find a group that is not going to try to summon you or harass you for not participating; fishing groups, grind groups, and open garrisions tend to work best. Try not to join instance raids or achievement groups.
5) 'Sign up'.
Upon joining the group, you should phase to the leader's server after a few seconds (a tad more if you are laggy). Check to see if your pet(s) are populated on the server you are on. If yes, capture the lil buggers, if no, drop the group and start back at step 2.
This technique is terribly handy when looking for jade oozlings, harpies, protowhelps, infinite whelplings, nexus whelplings, and all the other "WTF are they?" type pets. It's also super useful if you are trying to get stupid-hard to find ones like the minfernal and the giraffe.
Best of luck in your hunting!