I'm not sure if this has been mentioned yet, but capturing pets mid-flight between flight nodes (i.e. talk to Flight Masters) is possible, and it skips the CRZ nonsense.
Follow his instructions. It may take a few attempts, like he said, but it does seem to work. Additionally, follow the below instructions if you're having trouble with the Anodized Robo Cub:
1) Head to Nordrassil in Hyjal
2) Take the flight path to Everlook
3) Bind "Interact With Target" to any key of your choosing (Game Menu - Key Bindings - Targeting Functions subheading, scroll down about 1/3 of the way from the top)
4) Make the following macro and bind it to another key:
/target Anodized Robo Cub
5) As you approach Everlook, start spamming the target macro. When a Robo Cub is targeted, spam the Interact With Target key that you made.
6) Battle as you normally would and capture the pet you want.
BONUS ROUND: I fiddled around with this a little bit, but couldn't get it to work the way I wanted it to. Basically, any time you take a flight path between your realm and a CRZ, you'll remain in your realm until the flight ends. However, engaging in a pet battle mid-flight and waiting until you "land" (according to your toon's marker on the zone map) keeps you in flight limbo. When the pet battle is over, you will remain mounted on the flight master's mount, but you can control its movement! The range of movement is limited to a very small area - leave the area and you'll disconnect from the server. However, this window of movement - call it taxiing - allows you to capture pets not usually accessible due to CRZ, most notably the Anodized Robo Cubs near Everlook.
EDIT: This has already been mentioned by two other users, but their post count didn't permit adding links to their comments.