His highest level Pokemon, his Makuhita, is at level 18, so level 17-20 is probably a good range to be at. Keep Aron and Zigzagoon out of that battle, as both are weak to his Pokemon. Only bring them in as fodder if you need to heal another Pokemon.
I would very much recommend using Abra, don't just have it as an HM slave. If you still want an Abra as an HM slave, catch another. However, be mindful of Makuhita's Knock Off.
Both Grovyle and Lombre would probably do decently, so use them if Abra falls. But if you get around Level 20, you shouldn't have many issues.
Alternatively, I believe in Gen 3 you can skip Brawly and save him for later. If he poses too difficult a challenge, simply skip him until you're better prepared.
Hope I helped!
