Interrupts isn't something you can compromise on though, it would break all but the most trivial NES games (SMB and SMB3 both rely on interrupts).
I assume the trouble with interrupts is the "interrupting", as the location to jump to could be kept in a prefilled table like stormbrew suggested for JMPs.
If the target instruction-set doesn't have any way of "interrupting" that could be used, could it instead be solved by inserting a compact interrupt check between every "line" of assembly?