There is a simple strategy to finding one really. Feebas only appear on 6 random water tiles on route 119 out of 400 tiles. They can be found by simply using the old rod, but that's were the easy part ends. The best way to go about it is to fish in every tile of water 3 to 5 times. When I found mine I was jumping. It's a real pain in the ***, but had to be done to finish my pokedex.