Well you could have everyone roll a D6 and the highest one gets to move first that would make it hard to plan out the game for everyone.

Or you could take the number of battle victories that turn and use that as a basis of who goes first. The country that has the most victories has the combat initative and then gets to go first. In cases of a tie use the current IPC value to determine the tie-breaker.

Just a few thoughts.