Android Adverse To Dynamic Languages
Dan Bornstein gave a presentation on Dalvik at Google I/O. It's worth watching to learn about the system in general, including the constraints you care about. The specific issue of non-Java languages compiled into Java bytecode comes up during the Q&A.
Remco van 't Veer has a github project where he's patched Clojure to work on Android. Tim Riddell has written a tutorial on how to use it.
As mentioned here by @sean, there is sometimes a bigger problem than just performance. Dan Bornstein discusses it when asked about Jython, at ~54:00 in video. There is currently no support for dynamic languages which generate bytecode on-the-fly, (because the bytecode translation is not available at runtime).
There are some patches to make clojure work.
http://riddell.us/tutorial/clojure_android/clojure_android.html
I think the real issue is the use of byte code generators by some dynamic languages; they won't generate byte code for the Davlik VM. Therefore eval will not work.