One thing you can do, and this what I did, is you can fish in EVERY tile of water on the route feebas is found at least twice (I just went up the river doing this). I hear that there are only two tiles of water on that entire route that feebas can be found, and that its random in every game. I found one in less than 30 minutes.
I caught a feebas after only looking for a few minutes but I didn't get my first shiny until a few weeks ago (I restarted my Emerald and it was a lotad, the first wild pokemon I saw).