OCI is the Nios II JTAG debug module.
Be careful when using small caches since the smaller they are the more likely you are to thrash them and hurt your performance instead of helping. As for your question about custom linker scripts typically I just use the generated one, modify that, and point the system library properties to use the modified one. For more info on the linker script I would do a search for it since you'll find a lot with a google search.
As for your code changing on the fly..... otherwise known as self modifying code you can do it but you have to be
really careful (I would strongly caution you against this). If possible you may want to split your algorithm into smaller chunks that can fit into the tightly coupled memory then use a boothold to populate the memory (i.e. smaller algorithms that are stand-alone programs). A boothold keeps the processor paused so that you can copy code into its memory space for it to boot when you take it out of hold (hence the name). There is an example of a boothold component in this forum so searching for "boot" or "boothold" should find it.