I just realized that I do have D17 available on the custom board and its a hardware serial receive. I can use any digital pin as the TX for hardware serial, right?
Well you could technically use soft serial send on any port but D16 would be the hardware one that matches otherwise your receiving on one serial port and sending on another besides being ugly it should work. Are you using the mega unmapped pins pe2,pe6,pe7,pg3,pg4,pd6,pd5,pd4,pj7.pj6,pj5,pj4,pj3,pj2,ph7,ph2 I think 7 or so of them are hardware ints as well.
I2C is a good deal faster than serial and it's implemented in hardware. It's also multi drop so you can also connect sensors, eeprom, IO ex-panders, etc still using just those 2 pins. Since you seem to be running low on IO pins those IO ex-panders might be useful.
You did not mention what you wanted to connect the two atmega's together I assume it's not for increased processing speed.