I want to create a scenario challenge where the player can choose which side of the battle they want to play as in the same game. Is that possible or would I have to create 2 iterations of the same scenario?

probably the latter

Ask the players in advance which slot they’d like to be then allocate that slot in players with auto distribution enabled without territory limit.

If the game has already been created, players could leave and join the game until they get the slot they want.