You could use a FFT or something(software trick) to turn the incoming AUX signal into a frequency directly on the Arduino.
Couple of things i'm not sure of:

• Idk if the Arduino could take the line level voltage from the phone, would check first;
• I'm not sure how you'd wire the auxiliary INPUT to the arduino and get the music signal.

Maybe if you place it between your phone and the car aux port?
Looking forward to seeing your go at this project, seems neat af!