You want it all, and you want it for free!

One thought is that you could use something like 74xx652 or 74xx646 registered transceivers as storage between the two processor data busses. I'm thinking really simply mailbox registers here. You'll need some glue for decoding and enabling. These guys have registers or latches (depending on which part you use) on each side of the transceiver, so for example each micro can store its data-to-write in the outgoing register on its side, which the other micro can read at will. These register writes can occur the same time.

The second thing is you need some logic to allow each micro to tell the other that there's something new in the mailbox. It can be as simple as using the register write enable as an external interrupt source.

Of course, by the time you add the decoders and glue to the register/transceiver, it may very well be cheaper to use a 32-macrocell CPLD and put it all in one chip. Remember you need 16 flops to implement the registers themselves and the spare flops might be useful for some other part of your design.

-a