The only way to fine Feebas is to start at route 119 fishing on the top of the waterfall near the Weither Institute were you also can find a rare candy, some berries and a nugget (I say this, so you know were to start if you wanna capture it easily). Really, Feebas is one of the easiest pkmns to capture, you just need some patients! Trust me.
First: use an super rod all the time. You wil only encounter Carvanha at levels 30-40. You must look every tile on the water. If you do not, you may miss Feebas.
Second thing is that you REALLY must try every tile to encounter a pkmn. If it says not even a nibble but you dont met any pkmn you should try it again untill you met Carvanha. Just fish every spot for some 3 times after encountering an Carvanha. Then you move on to the spot next to the spot were you did fish but didn't met an Feebas
And I know now exactly were you can find an Feebas in my game. Everytime I look it is on the same spot and it doesnt go anywhere. ONLY if you go to Dewford town and talk to one of the peoples in the house called Trend whatever Phrase then you have search again cause it will be somewhere else

Feebas is level 20-25 so bring your pkmn that can make damage or sleep or with super effective moves and off course some ultra balls). It took me 1.5 hour but it was fun for me ^^ I even took care of the thousends Carvanhas wich made my pkmn stronger. So basicly, its up to you if you wanna spent some time with your gameboy/ds.