How do I get smallest NIOS2 code footprint possible?

You can write code without the majority of the HAL.

The boot sequence is that a small assembler stub sets up the cache and clears BSS, then it calls alt_main which sets up the drivers and calls main.

If you write your own version of alt_main then you can exclude all the functions you mention above. Of course a number of things won't work (like printf) but if you don't need them then that's no loss.

Replacing the assembler code at the reset vector is possible too, but probably won't gain you anything as you would have to write code to do the same thing.