Do I need external SRAM?

You will not be able to run code directly out of the EPCS device since there is a protocol involved instead of plain reads/writes. Long ago I saw someone post something in the old Nios forum that implemented this protocol. It would be very slow plus code doesn't access variables in flash block size sectors so leaving data that needs write access in the EPCS device probably wouldn't be a good idea/possible. If you can manage to find that component in here (it may have been copied over from the old forum) what you might be able to do is put the .text and .rodata sections into the EPCS device and put .rwdata, heap, and stack into on-chip memory.

Since the EPCS link is serial expect fairly poor performance from the CPU if it performs a lot of memory accesses to it. Slapping a small x8 SDRAM onto the board would probably be a better idea in my opinion if you want to keep the pin count low. Using SDRAM in half-rate mode will bring the interface hooked up over Avalon-MM up to x32 and would match the CPU width giving fairly good results assuming you add some processor cache.