http://playground.arduino.cc/Main/SpiRAM Here you go. You might be able to use the I2C pins to drive the chipselect and reset pin of the serial RAM while using the ICSP header for MISO, MOSI and SCK. I think that MAKERbuino contains all of these pins on a header so if you can make a good PCB, you might make a serial RAM expansion module.
Now, if this rendering and the recursions take up a lot of RAM, could you possibly remove the framebuffer and render the frame by sending data onto the display dynamically? That way you could get more memory. If not, how are you going to have the in-game score, lives, NPC data, SD-card library footprint and more?
In Atmel Studio, I saw that there's a neat feature where you can set up where your CPU stack pointer is initially. If you can be sure that you won't cause a stack overflow and if you can set up the stack pointer as low as possible such as at 0x700 and then have 256bytes for everything else, that might work well. Also, you can put the rendering engine's global variables into a union with some variables that are only used while you're not rendering the game such as when you're in the main menu of the game or the pause menu or something like that. That way while you're not rendering, that memory region is used for something else. Just be sure to re-initialize the rendering engine's variables after using their memory region for something else.
You can have every function check if the stack pointer has come too low before entering a new function. That way you can prevent a stack overflow.
If you'll have NPCs and as you say you don't have much RAM, you can have every NPC have a variable that says what it should do next such as move forward, shoot, turn, run, die, etc. and have all the behaviors pre-programmed as a script in the Flash memory.