Charmander can win consistently with some help (Potions or teammates) at level 11/12. You could get him up to level 14 or even evolve him if you want to be sure (incidentally, due to Charmander's parabolic exp. rate it hits level 14 faster than Caterpie hits 12). Charmeleon wins almost as quickly as Butterfree whereas unevolved Charmander is in for a long battle and lots of Growl while Onix Bides. Still an easy win though.
Caterpie's problem is it can't train itself. In Blue at least it can beat up other Caterpie, though it's very slow and you'll need to go to the Pokécenter a lot. In Red it gets whupped by Weedle. The only way to speed up the training is to do the switch-out method, at which point you might as well give Charmander that extra experience and have Caterpie catch up after Brock. It's not worth spending an hour to grind Caterpie just to say that the Brock fight took fewer turns than with Charmander.
For beating Brock in RB I'd say it goes Squirtle > Bulbasaur > Charmander > NidoranM >= Caterpie (might be close to NidoranM in Blue) > everyone else.
BTW I did a little testing. A pretty good way to train Caterpie is to switch it in on Rival 2, Brock, and all the Bug Catchers on Route 3. Let the pre-Confusion Butterfree switch in for a couple other kills on Route 3 and it should be done grinding by Mt. Moon.