There is another way to get fishing skill-up which is a bit of a mini-game. In Lower Jeuno there's an event called Moblin Maze Mongers. If you go to the goblin junk shop, you'll be able to get started with it. What you'll want to do once you've gotten started with it is rent a maze from Duplidox that has Voucher 08 Aquatic Depopulation Team installed on it. It doesn't have to have any runes as this should be sufficient for a beginner. Then you should allow your C.C. points to accumulate through inactivity of maze usage (I think the full 6 points occur somewhere around every 3 days after you last entered a maze). Completing the maze with full 6 points will yield a second additional chest which has a chance of increasing your fishing skill (I'm sure there is a Fishing level cap but I'm not sure what it is, sure doesn't give me any at 98 though).

The actual event though is a competition to catch fish and turn them in to defeat a brother pair. In other words, a fishing contest. There are monsters inside but they don't aggro (but they will eat your fish that you catch). There's also an NPC which provides you with a generic rod and bait though you can use your own as well. The maze is most fun when you have friends to help you (and even more fun when you have something like a Ventrillo server to communicate) but it certainly is doable solo. The fish within may also give you skill-up when pulling them up and they don't contribute to the fatigue you get from normal fish. It's something nice to do every 3 days if you're not using mazes for anything else. Also, you can even make it more challenging if you net yourself a Salinity Shift rune, though I recommend you practice without it first (you'll get freshwater fish without it and saltwater fish with it).