Wailmer
Go to the house near the water in Mossdeep. There should be a man standing next to it. Get the Super Rod from the man inside the house. Go down the steps of Mossdeep to the shallow water, where you can walk. Stand at the edge and use the rod. Wailmer will almost automatically start biting.