As someone who's taken up fishing in the last few months, my best fishing tip is, find something within 10 levels of your current skill (preferably closer) to skill up on. And I can not stress this enough... -use the fishing databases and figure out a way to isolate the fish you're looking for.- For instance, in Cape Terrigan, on a Halcyon Rod and a Fly Lure, you will catch -only- Cobalt Jellyfish, other than monsters. I wouldn't recommend this as a place to skill up fishing, but it's an example of catch isolation. (You find gilsellers there too, although I don't f'ing know why... you can easily catch a lot of jellyfish without the hassle of medium-high level monsters a lot faster in other spots... but I guess, with the IQ level it takes to be a gilseller, it's not surprising. I digress...) If you can find places to skill in this way, you'll thank Altana you did. Also, point number two: fishing skill comes sloooooooooooow. Do not expect more than 0.3/hr, although with wise location/catch isolation, you'll likely get more. Last thing: Invest in the fisherman's gear. That 4 fishing skill makes it that much easier. Really honestly last thing: Research research research. Nothing makes a bigger gil sink than doing something blindly for the wrong reasons.
Best of luck though!