There are two strategies for an Alliance Character to make a successful catch within Orgrimmar.
Firstly, there is a short bridge to a small entrance on the west side of Orgrimmar that goes over the Southfury River. There is a very small spot below the bridge that can be fished and counts for Orgrimmar. It is hard to get to the exact spot and may flag you PvP trying to find the spot, but few Horde players look down there.
Secondly, between the Valley of Wisdom and the Valley of Honor is a series of waterfalls coming down into the city, represented by a river on the map. Fly yourself to the very beginning of this river, high above the Orgrimmar cliffs. You'll notice that at the mouth of the river, your character is technically in Durotar, and not Orgrimmar itself, which means you will not be automatically flagged for PvP. Once you're there, face towards the way of the river, then jump onto the rock that is to the left, apart of the first waterfall. Then, turn around and face hat first "pond" where the river begins. While you are on that rock, you'll be within city limits and will be able to fish into that small body of water, allowing you to fish within city limits in a generally low-risk area. If you are attacked by Wind Rider guards, you will be able to jump and run the incredibly short distance back to the Durotar part of the river, which will despawn the Wind Riders, allowing you to heal up and try again. This method is confirmed as of 07Aug15.
For Horde, one way to do this in Stormwind without dying is to go to the right side of the entrance on the other side of the mountains blocking anyone from getting in by foot. Mind you this requires the ability to fly. Go to the right of the small stone building, cast your line and successfully hook a fish and then you gain the achievement, assuming you have gone to Orgrimmar already.