Is there a known way to export my wallet private key from the "Bitcoin Android" app (com.bitcoinandroid)?
I would try option 1 first, if you can find the right version of the library.  I'd be willing to try making a general purpose tool to do it, but don't have an Android phone.  Is there any way you can make a new, empty wallet and put a copy online somewhere along with a corresponding bitcoin address or two?

If you're attempting option 2, you probably know at least one of the addresses in the wallet, and so wouldn't need to hit blockexplorer for every guess.  You would expect the private keys to be evenly spread through the wallet, so once you've found a few you can make smarter guesses about where the rest are.