Your specs are contradictory, something at that low of a clock rate is going to be an embedded microcontroller and not have any external memory, hardly any external pins for that matter.
Really dont understand the desire for external memory, you can find 128K or 256K perhaps even 512K on chip, usually zero wait state.
To get those features you are going to end up with a considerably faster processor, that doesnt mean you have to run it that fast, but to get those interfaces and features you will end up there.
Expanding on the answers already given.
You should investigate an fpga solution. Lattice has a couple of soft cores as does xilinx, eval boards can be had from a number of places knjn.com avnet, etc. Too bad the $50 spartan3a board I have is no longer available. Opencores has many cores you can use, the zpu for example, full gcc compiler support. An fpga solution will allow you the maximum flexibility, perhaps more than one, one for the processor core with a generic memory interface then another for the video support, etc.
the PIC32 series is a mips so there should be tons of support out there, on chip memory sure...
Some folks have Atari 2600 solutions out there as well as amiga, you might grab some components from those efforts and mix and match.
rabbit semi now digi has some with 8/16 bit external memory interfaces. This is a modified z80 core if I remember right. Dallas now maxim had the TINI board with an 8051 based deal and I know it supported external flash, they wanted to run java so it may have had external ram. The sdcc compiler was known for 8051's if I remember right. I think renesas is another 8051 house, and no doubt you could find or build an 8051 in an fpga.
I highly recommend going with something arm based. atmel, st, stellaris (ti), a laundry list of others. Cirrus has an ARM7 with a cache and an external 32 bit memory bus, perhaps the arm9 version has external memory as well. You can buy boards from embeddedarm.com that use cirrus parts. Omap and marvell though are the ones to look for, granted you are looking at hundreds of MHz but the parts have what you are interested, external memory interfaces, video, etc. boards like the hawkboard, beagleboard (I really dislike the beagleboard, big ripoff, go for the chinese knockoff, like my hawkboards better but looks like there was a design issue), there is the open-rd (I like it much better than the plug computers).
You could dissect a gameboy advance, gives you a parallel interface, design something around the charmed labs xport.