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.)
MediaRecorder
and carry out signal processing? – SputterMediaRecorder
can only receive data from that camera and mic. Not the TRS socket. – HomeopathicAudioRecord
may be the solution. I will look into it. – Homeopathic