Eventually, after some discussion on a few mailing lists about using a new SASL mechanism for OpenPGP authentication, I decided to go the other (probably harder) way: OpenPGP over TLS.
I recently forked the python-gnutls project because it seemed to me to be unmaintained for a while. My fork is hosted on Gitorious: pygnutls.
I'll be primarly focusing on OpenPGP bindings and porting to the latest version of GnuTLS.
A working version of server-side OpenPGP authentication is already on git, next step is Android.
Android has no built-in concept of OpenPGP; it has a stripped version of Bouncy Castle, but not enough even for doing basic encryption stuff. So I will need to add Spongy Castle (+1.2 MB on the resulting apk) and possibly making my hands dirty by hacking on Bouncy Castle because RFC 6091 is not implemented.
I think implementing RFC 6091 turned out to be the best option afterall: creating a new SASL mechanism would have required prior D-H key exchange and all the other secure stuff already defined by TLS, thus reinventing the wheel. Not even talking about writing a RFC and making it accepted.