Parrot

I did find a few of these in Stranglethorn, but they're much more common in the Un'Goro Crater zone.  They seem to be in most parts of the zone.

These can be found as the primary battle pet, not just secondary.

I killed crabs along the entire coastline of Stranglethorn (Northern and Cape, including rivers) and came across a single uncommon parrot. It took over 50 battles.

Bloodsail Admiral am I, and adventured across open sea and land along side my trusty parrot have I.  But alas my hat he is much too fond of and of it no longer am I.  The smell of my adventuring and of things worse hangs heavy about it.  So I tasked myself to find another such companion to accompany me while I in my cleaner wear, even if be he only poor.  I found such a rare friend, and his rare cockroach friend, and as thanks for his friendhship I have sacrificed his friend.

The Dark Red and Black skin is the same as the parrrot summoned by the Bloodsail Admiral's Hat. If you can find one in that skin you can have the parrot with or without the hat.

Avalee is correct, I found one flying beside Watcher Biggs (alliance npc) half way between Splinterspear Junction and Stonard.

Confirmation: found these multiple times as secondary pets in battles in Northern STV.

Also find mine as the second critter in a battle in Northern Stranglethorn.

I found mine as an add-on in a battle in Northern Stranglehorn

Zenhunter does not seem to be wrong with regards to finding this pet in Stranglethorn.  I did not find one in North Stranglethorn but I found two in The Cape of Stranglethorn, both as another pet that had joined the battle.

Caught mine in a fight while looking for a rare Strand Crab in Stranglethorn. Tamed an uncommon because i didn't have one yet, and haven't looked back since! By far the best pet i have for fighting snakes, and regluarly masters snakes several levels higher.  

Mine summons in mostly white (the color when captured),some browns and a yellow. Just now, he came to a battle dressed in the Blue/red. Yeay! I'm wondering if the frequency of skin color is tied randomly to the pet, the region caught, or just a set factor.

I found him after engaging a Shore Crab in the Northern Stranglethorn, had to choose between an uncommon Shore Crab and a Parrot which I did not own at all.  I chose the Parrot.

You're wrong Zenhunter. Found one flying around near the entrance of Swamp of Sorrows.

Like some other pets, this one is only available if it "joins the fight". I've seen 2 in Cape of Stranglethorn, both were when figthing a Strand Crab.

Couldnt seem to find this one, all I found in those areas were polly's

The Parrot's skin changes each time it is summoned, in the same manner as the Worg Pup. This mechanic functions in battle as well; when you enter combat, your Parrot randomly takes on one of the available skins for the pet.

The number of available skins appears limited, however. The parrots I have captured in Northern Stanglethorn, for example, cycle through the brown speckled, white/yellow, and crimson/black skins.