This can be done in the tutorial area, and actually DOESN'T require catching the fish, it only requires cooking it. Head up the first set of stairs, then head left down the stairs towards the farm. In the chest next to the animal farm there will be some raw fish, intended for baiting ocelots. Take these fish and cook them in a furnace. The achievement should pop as soon as you take the fish out of the furnace. This solution is much easier than trying to actually catch a fish.

If you need any help feel free to PM me.