Is it possible to write a Vala application and get it to run on an Android device?
With the new NDK, you can write UI applications in C/C++ as well. As long as you have a C ABI, you can call anything from Vala you want, provided you have a .vapi file for it. The main obstacle is the lack of glib and gobject, but those can probably be compiled. After all, there's a Linux and a libc present.
Update: Bero Rosenkränzer did a nice presentation on the Android Builder Summit that shows the currently available ways to program Android without Java.