WAV/MP3 output AND MIDI output... simultaneously?

I have an interesting project that requires some guidance from you experts. I need to build a board that will play a song. Each song consists of two files: An MP3 or WAV file, and then a MIDI file that provides animation information used to control lights, valves, and other mechanical devices.

So basically I need to build a board that will play the WAV/MP3 file and output the audio to a speaker. At the same time, I need to play the corresponding MIDI file and send its data through a standard 5-pin MIDI out port. So the board will need a line-out for the audio amplifier and a MIDI output for some additional data signals.

My first thought was that I could somehow combine a standard MP3 Player Shield with another shield that will do MIDI output. The trick is basically playing these two media files at once and keeping them in sync. I see an MP3 library where you can query the current time of the MP3 file, so I could use that in the loop to make sure the MIDI file is in sync. But I'm not sure an Arduino can process this.

Does this sound feasible? There there already existing solutions for doing this? How would you go about building a project like this?

This is not easy if at all possible.
An arduino can't handle MP3 data directly and can only control a player.
A wav sound shield is possible but you can only open one file at a time on an SD card. What you might be able to to is to load the MIDI file into memory and then proceed to output the wave file. The main problems are that the MIDI file would have to be small due to lack of memory and synchronising the two would be very difficult.

It's not an ideal solution, but wouldn't another option be to have two boards, one for MP3/WAV and one for MIDI. If the MP3 board was playing the file and communicating the current time to the second board, then the second board could play the MIDI file and output the data of the 5 pin connector. It's not very elegant, though... that means I'd have to use two SD cards I suppose.

It is another option but you would be better off getting an Arduino with more memory, like a mega.

I know this is an old topic, but still very interesting. I am looking to do the exact same thing, but am looking for a software solution with a playlist feature. I was wondering that since you were asking the question to do this with an Arduino, did you already know of a piece of software that did this on Windows, play a wav/mp3 file and a midi file at the same time in sync with a playlist feature?