http://www.sqlite.org/rtree.html says that the r*tree is "included as part of the amalgamation but is disabled by default" and to enable it "simply compile with the SQLITE_ENABLE_RTREE C-preprocessor macro defined"
Well I want to use R-trees in my android app, but clearly SQLite is all pre-installed etc. Is there a way to enable it on a user's phone/device?
Alternatively, is it possible to use the NDK and the freely available source code for SQLite?
You can absolutely compile your own version of SQLite. We do this in order to enable the encryption/codec modules from wxSQLite. Take a look at the SQLite source in the Android Git repository. Basically it's as easy and creating a Android.mk with the options (such as SQLITE_ENABLE_RTREE) you'd like enabled. Of course, this will give you a native library. In order to use it you'll need to access it from the NDK or create a wrapper (again, you can look at the Android repository and Java/JNI wrappers to SQLite)