And don't forget about the Drinks from Celadon's department, those restore a lot of health for a cheap price!
I personally prefer Two Island at Sevii for getting drinks. You have to go through the trouble of going to Vermilion and taking the boat, but you can buy in bulk.
In any case, I'm also having trouble training against the Elite Four, which is annoying since I had no trouble raping the Sinnoh E4 (partially because my stuff was level 64 there). I think my problem is largely type coverage rather than levels, but I'll let you guys judge.
Pigeot lvl 54
-Wing Attack
-Fly
-Quick Attack
-Featherdance
Raichu lvl 55
-Thunderbolt
-Quick attack
-Slam
-Thunder
Dragonite lvl 55
-Slam
-Thunder Wave
-Twister
-Wing Attack
Magmar lvl 58
-Smog
-Fire Blast
-Confuse Ray
-Flamethrower
Blastoise lvl 57
-Hydro Cannon
-Bite
-Surf
-Skull Bash
Sandslash lvl 55
-Cut
-Slash
-Sand Tomb
-Earthquake
I tried running with approximately this setup with slightly higher levels (used Rare Candy but reset without saving afterwards), but ended up getting almost raped by Agatha, so I decided to go back and train them up somewhat, which is where they are now. I have a lvl 48 Kadabra in reserve, plus the three legendary birds UT, but I wanted a challenge so I dropped Kadabra, and I planned to Dongle the birds to my Pearl cart and trade/EV train them there.
Unfortunately, I don't see a whole lot of options here besides raising the levels on my team. I was thinking of replacing Skull Bash on my Blastoise with Blizzard so that I could rape Lance more easily, but the inherent inaccuracy that comes with Blizzard sucks, so I'm thinking about getting Ice Beam at the Game Corner instead (which will rape my wallet).
My Pigeot is largely useless compared to my Dragonite, and since Fly only gets 70 STAB in Gen III instead of 90 in Gen IV, it can't hit very hard, and its move pool isn't highly impressive in Gen III. I'm thinking of dropping it for my Kadabra, which would fill up my Psychic type coverage gap.