PLEASE NOTE: THE ANSWER BELOW IS HORRIBLY OUTDATED, AND MIGHT NOT BE ENTIRELY CORRECT ANYMORE.
You can program in C/C++ using the Android NDK. You’ll have to wrap your c++ codebase in a static library and load that through a Java wrapper & JNI.
The standard NDK does not support RTTI and a lot of the functionality of standard c++ is also not available such as std::string, etc. To solve this you can recompile the NDK. Dmitry Moskalchuk supplies a modified version of the NDK that supports this at http://www.crystax.net/android/ndk-r3.php. This modified version works on all Android phones that run on an ARM processor.
Depending on the kind of application you should decide to use Java or C/C++. I’d use C/C++ for anything that requires above average computational power and games — Java for the rest.
Just pick one language and write the majority of your application in that language; JNI calls can decrease your performance by a lot. Java isn’t that hard though — if you know how to program in C/C++. The advantage of Java is that the application can run on any device running Android, where as NDK applications depend on the architecture it was compiled for.