Exchange C167 by FPGA and?

Really the only way to find out is to try to put your existing code through gcc and see what problems there are.

Even compiling it for x86 might be informative - although building a standalone gcc for nios is fairly easy (info on the wiki), and that will give a more realistic idea of the size.

If you only have a small amount of C code, and don't need anything thing like TCP/IP, then you can easily build something that does need any C library support. Everything will then (probably) fit in the internal memory.

The ability to write 'custom instructions' in VHDL can help speed up the code without requiring massive and complex VHDL blocks.

Debugging the C is also probably easier - and it goes wrong in more predictable ways! Especially if you write an avalon master interface for some external bus in vhdl (possibly multiple 8 bit transfers, or even a serial port!) that lets you read (and maybe write) any avalon address while the system is actually running.

This is probably more use than the jtag debugger - as it lets you debug the code running in its production environment. Depending on that environment it might also be used to download the actual code.