Bluetooth module to have microcontroller communicate with Android phone?
I know this is an old thread, but it might still deserve some attention...

Bluetooth on Android is mainly used for connecting to wireless headsets. Wireless headsets are slave (not master) devices. This means you'll be able to connect to your slave-only cheap-o Bluetooth module. In fact, I have one of those modules ($6 on Ebay), and I just successfully paired with it from my Nexus S.

It also seems like you can program your Android phone to do anything you want with a Bluetooth link (see this question on StackOverflow for instance).  The slave-only Bluetooth module should be sufficient for your needs: you do not need Master mode to transfer data bi-directionally.