I'm pretty sure it's too late by now for Python, but I've had some success with compiling C-based interpreters [0] to C; that is, generating the actual C code that the interpreter would execute to run the program. That way you can reuse much of the interpreter, keep the dynamic behavior and still get nimble native executables.