Did I miss anything? What are the relative advantages of each solutions? Do you think that I overlooked other options? Would using an exiting virtual machine be a good option? Except for Nice, this option doesn't seem to be popular; there must be a catch.
You might want to have a look at the LLVM project. It has an intermediate representation that is a bit simpler then the one used by GCC and can be dumped to disk. Rafael