well, just feed feebas with any kind of pokeblock that rises beauty until it can't eat anymore. then level it up. I think there are no pokeblocks in fire red, you'll have to trade feebas to ruby, sapphire or emerald, or migrate it to D/P in order to evolve it.
[center]
Signature and avatar images by me.