First step I did a /who of Tol Barad there was only one warlock on the island, so I figure why not? I ask the guy and he says sure he'll find some people. I was really surprised the first person I asked was kind enough to do this. Few seconds later I get a whisper saying he's got two people and I'm summoned in. He tells me good luck and I start my adventure.
I start out being summoned in at the Alliance starting area here is a map of the route I took via the water. Note: I mapped a possible Horde route as well though I haven't confirmed there are no sharks in that area. From the Alliance path I spotted no sharks at all even with beast tracking on.
Now I get to the village and I watched the gulls for a bit trying to edge in close enough to hit tame, but bad news bears, you can't get close enough at a very low level without aggroing at least one of the pats. Though possibly you could time it right as they normally run off the dock and down through the water to get you leaving an open cast time providing your quick enough.
However; the gulls will actually get up and circle around:
At one point they will get close enough for you to hit em with a Concussive Shot to pull them providing you can turn around quick enough and turn off your auto shot. They'll fly straight to you and you can tame them without having to worry about the guards at all. I noticed they fly this path every few seconds too which is pretty good.
Then all that's left is to tame your birdy hearth out and have fun with em.
Named mine Salty. :p
Congratulations on your birdy, you earned it!