Pewter? Just make sure you have some rapid-attack pokemon, like a mankey with fury swipes or something. Also put a paralysis-enducing pokemon on each side of the gym. I got a Squirtle as my starter so it may have been easier for me, but it probably wasn't too much easier.
If needed, do some level grinding.









