Here is how I completed this quest.

Velia Beach (Left of Velia)
Fishing Rod (You can buy it from NPC for 500 silver)
if the first fish is not a Sea Eel, go back and restart the quest
once the first fish is a Sea Eel, the rest of the fishing will use 9 energies (Whenever I use 8 energies I get extra green or a chance at blue, if I use 10 energies I start to get more yellow fish which isn't what I want)

P.s. I completed the quest with Skilled 2 Fishing, started from Beginner 1

Good luck!

1. Terrmian Fishing Rod / Tripple-Float Fishing Rod
2. Food / Buffs to get 5 Fishing lvl
3. Use Nrg not for rarity as in the comment above, as it does not work that way.. Use Nrg for a chance of an ADDITIONAL CATCH!
4. (optional) Maple Float will help you get less Green catches
5. Do as written above - restart Quest once the first catch is not a Sea Eal.

Ps. I Started quest on App 1 and finished it on App 1.. Just boost the rarity of the catch and the amount of fishes you pull out with one catch. If you do so, this quest wont bother you at all