There's also the possibility to use some kind of audio compression , though it makes things both on the phone side and the other half more complicated.

There's been just the teensy 3.1 released, a tiny board with a 72mhz cortex m4 muC, 64k of ram + 256k flash, has dsp extensions, two i2c busses, spi, can,usb, some adcs and one 12 bit dac, Arduino-compatibility, and below 20 euro. Bit of an overkill just for an fm toh maybe, but could be a nice base for many projects:

www.pjrc.com/teensy/teensy31.html