If needing an interpreter is a problem, have a look at Perl. It has been proven that parsing Perl is equivalent to the halting problem, and functions can be created at runtime so it could give you a lot of trouble.
Well, the problem isn't the interpreter; it's trying to get low-level code to do the same thing as the interpreter without a VM.
Runtime function generation will definitely not be a problem

Reflection will be a little harder to implement, but still possible.
I think I need to see more detail, though I still suspect that the alternative paradigms will cause you trouble.
Probably, but it will still be fun and useful
