For such a large amount of memory - you really have two choices:

1/ SDRAM (dram). Yes, the refresh is an issue that can be solved with a cpld or small fpga. You'll probably need one of these anyway to do the page addressing. Do you need battery backup? Another solution came to mind in that you use another cpu to do the refresh and address mapping rather than dedicated hardware- the issue then is comms between the two cpus. Refreshing is really just a matter of doing a refresh cycle on all the rows within 2mS (I think - it's been years since I've touch dram) - so you could use a timer interrupt to schedule this - so want want a very speedy micro to make this efficient.

2/ Flash. This is probably the cheapest for bulk storage. Downside is that it is a bit slow to write.

I gather you're doing some sort of data logger - so maybe you need a chunk of sram for your buffer and flash for the bulk storage.

For my kart datalogger, I took the easy route of using a HP IPaQ as my data store and GUI with a little micro doing the acquisition work.