At the moment it looks like even though lots of nodes relay transactions with a 0.01 mBTC fee per kB, miners don't care. They still require 0.1 mBTC per kB.
How do you verify this, or where does this conclusion come from? I typically send all my transactions with a 10 bit fee (at least when paying from a wallet that allows custom fees, such as MultiBit or blockchain.info/wallet) and I never ever experienced any problems.
If you want to experiment with fees, feel free to build your own binary from the source.
I'm pretty unexperienced with Android development, but I'll look into it, thanks.