It all depends on the start condition.
If one Arduino is the master and always switched on as the first one, it is not so hard.
But even if both can be master and switched on and off at any moment, it would still be possible (I think).
Suppose you have RX and TX with SoftwareSerial,
http://arduino.cc/en/Reference/SoftwareSerialThe TX can be recognized if some kind of "synchronisation byte" is sent for example 10 times a second.
The RX could be default high (with a weak pull-up) to distinguish it from the ground.
You would need only three wires. After recognition, the SoftwareSerial can set a serial port on those pins.
The ground could be an output pin set to LOW to be some kind of simulated ground. It would need some protection for ground currents, but I think it is possible.
With I2C, I can't figure it out, how to do it.
With SPI should be possible, but harder to implement than the SoftwareSerial.
OneWire protocol. This would be possible. I don't know a lot of it, but it's a single wire and data can travel in both directions.
In the end, I would prefer a real ground (not a simulated ground with a pin) to both Arduinos. And 2 wires for TX and RX.