Here's what I just did for my board.
I have an ATMega1284 (5v) and an LPC1227 (3v3) sharing a 128kB SPI serial SRAM. The 5v side is the master and it has control over the MUX. Each chip's CS signal goes to the other and they will be used for handshaking.
It seems like the and gate outputs are acting as a sink when not outputting a high rather than floating.
Umm yes, an '08 has a push-pull output so if it's not sourcing current it's sinking current. AFAIK there are no chips that "float" for a low and drive for a high. The reverse is common though, look for "open-collector" or "open-drain" outputs. If you want to continue with this approach the 74xx09 might be better, that's an AND gate with open-drain output.
i may actually just add a secondary smaller ram chip on the other side of the setup
This is by far the easiest approach.
In my case the RAM has to be shared because that's how the CPUs communicate, but you can use serial. That said it will be MUCH more efficient to share the RAM because the data is only stored once, not stored and transferred and stored again.
The tri-state approach is simple and will work as well, it's just that there are no guarantees you will get the code right, even if you test it to kingdom come there will be a path you never thought of that will pop up one day 
Also it doesn't help with the level conversion. Also if you need to store 32kB of data it won't work with the small AVRs we use on Arduinos.
Rob