Please check this site for some Cortex-M3 platforms that support Linux (uClinux):
http://www.emcraft.com/
We successfully run uClinux on the following Cortex-M3 MCUs: NXP's LPC1788, STmicro's STM32F2, Actel's SmartFusion, and are in process of adding support for a couple more: Freescale Kinetis, STM32F4 (these two are Cortex-M4 rather than Cortex-M3).
True, Linux (uClinux included) requires external RAM to run - the integrated SRAM of Cortex-M is not nearly large enough even for an ultra-tiny Linux configuration; you need at least 4MB of external RAM for practical configurations. The more the better, in fact - if you application needs "features", Linux has support for about anything and you will not be sorry that you have added more RAM rather than less.
In respect to particular devices to use for external RAM, it all is defined by the external memory interface provided by a particular MCU. STM32F and SmartFusion support only SRAM; you would be able to get a 16MB 70ns PSRAM (with a Page Mode for faster operation) for $6-7; LPC1788 support faster SDRAM memories; Kinetis K70 supports DDR2 ($5 for a 64MB device), etc. All those memories draw power at just uA levels at static times.
You need something to load a bootable Linux from, but this can be about anything - network, SDcard, SPI EEPROM, NOR or NAND Flash, etc.
Overall, I daresay that Linux is a totally practical option for a Cortex-M3 design.
Update
There are plenty of power-sensitive applications where your device is idle most of the time, however, when running, it needs to be able to do many things that are not going to be easy to achieve using a smaller RTOS. Secure connections, VLAN, TCP/IP tunneling, SNMP, SD Card, USB device / host, WiFI, etc and the list of requirements goes on and on.
With a smaller RTOS some of those features will be available, some not, however it is only part of the story. What we are seeing with our customers more and more is that embedded designs using Cortex-M3 need not just 1 or 2 of those advanced features, they need many of them from a single device. Even if an RTOS provides all features a design needs off-the-shelf, cramming it all into the on-the-chip memory is going to be a challenge. uClinux or not, my guess is that the trend is going to be that more and more Cortex-M-based designs will use external memory. Of course, once you get external RAM in your design, uClinux starts making more sense.
Regarding low processing power provided by Cortex-M (as measured against the requirements of the Linux kernel), as a recent experience, we have just enabled uClinux on the Freescale K70 MCU. This is a Cortex-M4 (which is the same as Cortex-M3 plus hardware FP and DSP units); on-chip interfaces to high-density RAM (DDR2) and Flash (NAND), with 2x8KB on-chip caches. 120Mhz Cortex-M core, with 150Mhz parts coming out soon.
Linux (uClinux) runs just beatifully on this device. Using 'dhrystone', we get about 50% performance we get on a 250Mhz Freescale PowerPC box. Fast boot-up, lots of RAM (the TWR-K70 module provides 128MB of RAM and 256MB of NAND Flash), networking, JFFS2, framebuffer, SSH, HTTPD, Qt/E - all this runs just fine on K70. Overall user experience is your regular "embedded Linux" on an MMU-full microprocessor.
Here is a pointer to the video of a live uClinux session running on the Freescale Kinetis K70 Cortex-M4 MCU:
http://www.youtube.com/watch?v=UZjJrLG9CeA