There's no minimum level requirement to fight the gym leaders, or players for that matter. The level cap is in place so players can't grind their Pokemon to level 100 before the 1st gym. It would take FOREVER but, without the cap, it would be possible.
Here's how I do it: I make my way through the story until the gym leader. If you don't over-train your Pokemon, you shouldn't be anywhere near the level cap by the time you make it to them. Once you've defeated the leader and all their gym trainers, you should be a little closer to the cap. While you're able to battle other players at this point, it would be wise to train your Pokemon up until they reach the maximum level for the current section, just to get that extra boost to your stats and maybe learn a few moves, you know?
In short, no, you don't have to be level 25 by the time you battle Brawly. You just can't be over level 25 when you're battling with us! :)