I would say compiled Scala runs well on the Dalvik VM.
All languages that do not need to generate (or load) class files at runtime should work well on Android. And that is because Dalvik does not run class files.
So then why don't we see more non-Java Android apps in the wild? We can only go off of open source apps, I've looked at quite a bit of those and have ran across only a couple that don't use Java.