You are basically asking how to turn the microphone input into a modem input. A variant of this clever technique is used commercially by Square for their magstripe readers on both iOS and Android devices.
To do so requires getting access to the raw PCM stream from Android and decoding the input. Luckily for you, someone has already done it and thrown the source out there. See this Hack a Day linked project for sample Arduino and Android code for transmitting only.
I couldn't find example Android code to receive, but there are rather extensive notes on doing FSK with iOS in this Arduino forum post.
(Though it wasn't your question, an easier way to get data in and out of an Android device is the new USB Host and Accessory support. It requires a newish phone and OS, so not as flexible as the audio route.)
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…