Hello AlexS,
I'm also designing a custom board with a EPCS16 device, and I have thought about your problem. I think you are right, EPCS16 is not supported with nios 1.01 software. I think it's yet available a new version of the nios software, 1.1, but I don't know if this serious problem is there resolved.
I'm thinking about the posibility of programming the flash memory with a programm made by myself through the debbuger, by using the HAL functions for the "EPCS Device Controller Core with Avalon Interface". That may work out, but there is a problem more: Some of this functions read the ID for the EPCS device, and they don't consider the ID for the EPCS16 (I think is 20h). Perhaps you can change a little these functions and get the problem resolved.