I think 2 wires is all that is needed - Gnd on both sides, and then any 1 pin to any 1 pin.
Have both sides start as all pins as Inputs, listening for a low on any pin, pullups enabled.
After some arbitrary time (each can have random seeded millis() that it waits for) each side uses pinMode (pinX, OUTPUT) and asserts a pin low for some brief time ,then goes back to input mode. If the other side sees it, it asserts low back and then waits for a 'fast' burst of high/lows for a 1, or a 'slow' burst of high/lows for a zero.
Repeat that back for the receiver to show the sender sync has been estalished. The fast/slow bursts become like a slow software serial.
Each side could use PORTx commands to quickly look at its 3 ports for a non-0xFF (or masked for the bits to be used) to see of a low was asserted by the other side. The Low would have to be asserted long enough for the 3 reads to be able to catch it, and after seeing a low, the initial receiver could assert low for a longer time for the initial transmitter to catch it.
Or something like that ...