As Luka said. The MySQL database would be a single thing to take care of. It would also let you advertise that you want a battle and match you up with someone automatically, rather than having to find someone via other means (e.g. messaging, posting in a thread) and then set up the connection with them yourself. It'd all be self-contained and convenient.
Hmm, perhaps setting the RNG seed of both players to the same value would help? Theoretically that would make the battle at both ends play out identically given the same inputs, and all you'd need to transmit is the information of which action is taken each round.
Okay, you're not so brave. :D It actually sounds manageable now.