Well, the only way that catching Feebas can be easier that doesn't involve cheating is to have a friend that has Feebas, so that they can either trade one to you or mix records with you so that you will get their Feebas tiles. Outside of that, you just have to keep searching. Make sure that you encounter 3 Pokémon on each tile before moving on, just to try and eliminate the possibilty of missing out on the Feebas tile. Here is a thread that is in the R/S/E FAQ forum about Feebas, you could take a look at it, it could help you out some. http://serebiiforums.com/showthread.php?t=2802
Whatever you do, don't change the Trendy phrase at Dewford, that will just change all of the tiles around and make for more confusion, and it will take any longer. Really, patience is the key. The Feebas tiles are there, it isn't really so much a matter of luck as finding a shiny is, it is just a matter of finding the correct tiles.
If you have any more questions on the subject please post in the sticky that Stardust25 provided, it's the official thread on anything related to catching Feebas.