Trivial for the MP3 part. An embedded Linux or FreeBSD system that runs on a "microsystem" and boots from flash is extremely simple to construct from off-the-shelf components, and the basic codebase is open.
The hard part is the interface to the changer system, along with the level matching (e.g. the audio side) required to get things to work "right". The latter has to come online almost instantly when "turn on" is called for, otherwise the head unit will declare the changer "broken" and refuse to talk to it thereafter. You don't want the entire system powered up all the time due to battery drain issues, so you need a two-CPU-style design, where the interface chip runs from an on-firmware codebase and thus can be available immediately when turned on.
How much of this can be done without running into an existing patent (that is, designing AROUND any existing patents) is another question. Irrelavent for personal use, but if you're going to MAKE these, its very relavent.
BTW the latter piece HAS BEEN available for some head units. There is/was the "VWCDPIC" out there for VW units, which is a tiny microcontroller that talks VW's head unit protocol, has two RCA jacks on it for audio in, and passes the protocol out via a serial interface (!) so you have bidirectional control (you can set disk and track numbers, etc.) My understanding is that VW got pizzy with them about their reverse-engineering and this nice "postage-stamp" size thing may no longer be available (I have one though!)
