A level would be helpful, ya know...
Anyway, I recommend finding people with the Match Call and using Sharpedo against their pokemon. If it's freshly caught, it should at least be able to take a bite out of the trainers' pokemon, especially those around the Mauville area.
If you're using Sharpedo for Tate and Liza's Gym, bear in mind that their Solrock knows Solarbeam and Xatu sets it up with a Sunny Day.