This is how I would do it: if there are any open "network" slots, clicking the "start game" button would prompt the user if they want to start with AIs controlling the empty network slots. Clicking no returns the user to the custom game screen, while clicking yes would prompt the user to choose the AI setting (easy, normal, ultra, mega). For simplicity, probably best to use the same AI setting for all these network-AIs.
Anyway, the game would play as normal with the AIs until a user tries to join the game. For this person joining the game, they'd see the game on the master server as usual and would get the same custom game screen, but none of the options would be changeable (so basically just a preview of the game's settings). The only thing they can do on this screen is choose a player to take control of. Choosing one of these will make main host get a message that this player wants to join the specified player's slot (and should state the faction and team). If it's reasonably possible, this prompt should pause the game (for all players) and it should be possible for the players to chat amongst themselves while the prompt is still up, allowing them to discuss if they should let the player join. If also possible, their chat (provided it's set to "all", not "team") should also be displayed to the joining player, allowing them to tell the joining player things like "join a different slot instead".
If the main host chooses "no" to this prompt, the joining player is not allowed in and cannot submit any more prompts for this position. However, they can choose a different slot instead. This "ban" only lasts for the single game. Presumably the existing methods of banning annoying players would still be in effect as well (though I'm unfamiliar with the workings of these).
For a very rough first implementation, it could be possible to skip the pausing and ability to talk to the joining player, although it would be much more limited.