I believe I could do static recompilation for programs that run on a barebones environment and do not employ self modifying code. The more general problem of finding all executable code in a blob of arbitrary binary data (which I would have to solve if I wanted to run an arbitrary program unmodified, which I do), is equivalent to the Halting Problem, so that is a no go. This means that, to have a general solution, a hybrid approach of static and dynamic recompilation would have to be employed.
For well behaved programs, code generation on the fly does not pose a significant overhead (that's what the profiler tells, if I recall correctly), so I'm not sure the hybrid approach is worth its weight in complexity.
Besides, I don't know if I'd be able to run a full OS, though, because those need interrupts (in my case, currently there's a timer tick and the UART interrupt when input is entered through the keyboard), and I haven't thought about handling that.
I'm actually working on a JVM interpreter in Coffeescript now, so this topic is particularly interesting to me. Thanks again for taking the time to explain things.