Gym Leader rematches can only be obtained after you get their number, and call them on a certain day in which they will appear at the Fighting Dojo in Saffron to battle you. Then after you beat them they dissapear, and you have to ring them again at the correct time. You can check here for stuff like that. The Gym Leader rematches normally have Pokemon from the low 50s to low 60s in level.
This as well as rebattling the Elite 4 is a good way to train to beat red. The Elite 4 are at higher levels on your rematch with them, the lowest being 58 (Will's Bronzong) and the highest, 75 (Lance's Dragonite).
Wild Pokemon battles do take forever, yes :P. However, if your Pokemon aren't up to scratch to beat the Gym Leaders/Elite 4 without heavy use of items and stuff, the best place is to train at Mt. Silver. The Pokemon here range from anywhere between high 30s to low 50s in level.
Also, Red is in Mt. Silver. His Pokemon are extremely powerful, from level 82 to level 88. The most dangerous is without a doubt his Pikachu, who is the highest level and also has Light Ball, boosting it's once lackluster offenses to deadly levels. It is recommended to have a diverse team of level 75+ to vs him, though it will be easiest if your Pokemon match his levels, or surpass them.