I think the Cortex M4s that are coming out have 512 kB and up in their bigger variants. They also have more MHz and MIPS, and just need a cheap board available. The TI Stellaris Launchpad is looking good in this direction.
The Stellaris tops out at 96KB SRAM (and the part on the Launchpad is 32KB). I'd be interested to know what parts you're looking at, as right now I'm looking into building an SPI-based RAM expander for the Stellaris board.
Regardless, I believe Torne was saying that Python ends up needing a few megabytes to work. So you still pretty much end up needing something with external RAM.