Говорят, что ART (новая среда исполнения Android) поддерживает LLVM, и возможности Native-разработки расширяются.
Сам немного писал Native-код по книге Android NDK Beginners Guide. И немного своего. Можно указать компиляцию для всех платформ и тогда в APK включается обертка на Java и сразу три библиотеки - ARM, x86 и MIPS.
Думаю, Java из Android ни куда не денется, даже в свете последних судебных решений, но как вариант можно писать и на других языках.
Есть еще HTML5. Видел, как его превращают в APK, но то, что я видел жутко тормозило.