I've sent a transaction which has a <0.01 BTC output, with zero fee using blockchain.info Android client. It is not being relayed (violating memory pool rules of bitcoind). What can I do to recover the Bitcoins that participated this transaction?
You can do two things
Wait until the transaction gets relayed. Transactions without fees usually get relayed as well, but often a later than those with a fee.
Send a new transaction spending the same outputs, with a fee. It's possible that some miner will accept it eventually. This can be tricky when you use blockchain.info's wallet. It's called double spending, you can probably find some information on that elsewhere, like on bitcointalk. That article suggest that you import the private key from the address you send from to Bitcoin-Qt and try to do the same transaction again from there.