Only two playthroughs are required, but one of them has to be of the Advance Campaign.
COs only become available in Battle Maps after finishing a campaign in which you completed their unlock requirements, as follows:
Grit: Choose Max for Mission 4, "Max Strikes!"
Eagle: Complete "Captain Drake", "Naval Clash", "Wings of Victory", and "Battle Mystery" with ...
I don't think you can do it without restarting your whole game. However, if you press L + Select + Right directly after turning on your GBA, the delete data option shows up allowing you to delete the data.
GameFAQs Advance Wars cheats
All Advanced Wars game I've played, Dual Strike and Black Hole Rising, have this limit. I'll assume the original has it too. It's usually very difficult to hit this limit while playing campaign, war room and versus against an AI, but you can see this limit when designing maps:
The left is the number of units you can place (50 since there are no units on ...