This can be done, and I have already loaded the Linux kernel into the SRAM. I had similar thoughts of moving the kernel from RAM to flash; However, the flash becomes an issue when I try to load the file system. The only way I know how to load the file system is through the flash-programmer.
I'm going to try to reconfigure my Nios core. I currently have two 16-bit wide sticks of flash configured as one 32-bit wide flash. I'm going to separate them in SOPC builder and write some VHDL code to do the address decoding. I did something similar for the SRAM, and it works just fine. I'm hoping this will work for the flash as well. I'll post a success or failure when I'm done. I don't think I'm going to get back on this again until tomorrow.