Note that a processor that can run "directly" from a serial flash will not only be limited by the interface using one or four data lines. It will also be breatly hurt by the core being totally unable to run from serial memory. So the memory controller may be able to read data from serial flash to fill some form of cache logic within the chip. But whenever the processor runs out of that cache, it would need to stall while the memory controller reads more data. It just isn't possible to "just" scale the execution speed in relation to the memory bandwidth.

The faster cores are normally much faster than what flash memory can support, which is the reason already 50-100MHz ARM ARM7/Cortex-Mx cores have some flash caching logic, and the even faster chips prefer to copy the code into RAM first.

Your choices will improve if you are ok with large-pin-count chips designed for use with external memories. In the 400MHz range, there should be a number of ARM9 chips available. Maybe a Freescale chip?