Arduino Mega 2560 like board but with more ram
Try using an I2C SRAM chip. 

Maybe a 256 kbit N256S0830HDA @ 3V from AMI fits the bill:  http://www.modtronix.com/products/components/ram/n256s0830hda.pdf

See http://arduino_related.livejournal.com/1414.html for a tutorial.