For a restricted subset of Javascript it wouldn't be that hard.
I'm not sure that solves the iphone problem though - I don't think it's kosher to use non c/c++/objc code. A Javascript to C compiler would work fine, though. That would be quite a bit more work, though.
[Edit]As pointed out below, it might well be ok. I guess you'd have to somehow get the generated machine code into a static library and link it with your application. That might work.
I wonder how feasible it would be to pre-compile the Javascript to machine code before distributing it? Maybe someone determined enough could probably hack one of the existing JIT engines to emit executable machine code to a file?