I've created a utility to let you patch the instructions in your ELF.
This is handy if you want to use custom instructions instead of some normal Nios II instruction (e.g. multiply, divide). Just run it without any command-line arguments and it will give you usage. The tar file contains Linux and Windows versions.