I don't know if it would be that difficult. What you thinking of already exists - it's called USB On The Go, usually USB OTG.
My phone (now nearly two years old) has this, and it means I can either plug it into a computer as a mass storage device OR I can plug a mass storage device into it. I can also plug a keyboard or a sound card into my phone.
The key seems to be that fifth pin on the Micro B connector. There are Micro B to Micro B cables (I have several) but they have one key difference -- one end has the ID pin grounded, the other lets it float. Thus, the cable determines which device is client and which is host. They are usually called "Micro B to Micro B HOST" cables. The USB shell on both ends is identical, with the only difference being the ID pin as described above.
All this would be meaningless except that I have seen application notes indicating that the ATmega32 can actually do USB OTG. Perhaps the ID pin connection needs to be somewhat standard (and I have NO IDEA what standard is for this platform), and then it could be possible that two Arduboys could be connected with a cable for head to head games. I do know that the Arduboy is somewhat "USB flexible" since they show the idea of using it as a custom keyboard.
Perhaps someone with more background on the Arduino platform can chime in. I think this is a key item, and I have been looking for info before I finalize my backing. More particularly, I was actually looking for circuit diagrams, but (not surprising) did not find them. If the simple connection of one pin in the USB connector is all that is needed to make this work, then it would be worth letting Kevin and his team know about this possibility.