The zilog Z180 bills itself as an 8-bit processor that can be used to decode digital CD data and play as output.. it runs 20-30mhz.. but big difference is that it supports external RAM which can be utilized thru a minimum of 3 8-bit ports... Something the Arduino doesn't have..
You would waste a lot of overhead just trying to handle enough memory to do anything useful with audio. With only 1k of internal ram you are limited into how big of an audio sample you can read in. even at a low 8khz bit rate that's less than 1/8 second sample. FYI: most MP3 files have 128k or higher bit rates..
Your best bet if you really want to do something like this would be to manipulate the audio to match a specific baud rate with slow on-off pulses and treat the data as serial input to the arduino.. This would require the least amount of processing power, hardware or 'glue' (IE support IC's to convert audio to ttl data..) You could practically just wire one audio channel to ground and one digital or analog pin..
Since you mentioned wireless bluetooth.. you might consider something like sparkfun.com's blueSmirf.. it is serial bluetooth adapter and you can just feed it serial data from a PC or similar.. maybe even java running on a java-enabled phone..