How do you know you can't do something if you haven't tried

Player Piano

Take a player piano, <$300 on  replace the foot peddles with a vacuum pump.  Remove the vacuum tubes that route to the sheet music mechanism.  Attach a series of pneumatic air valves to these lines, run these off an Arduino with some code to process Midi and bobs your uncle.

Now if only i could find a cool looking player piano that didn't look like it was from the 1800's

My only requirement is that it would be able to play this Black Midi song.

MIDI itself does not make sound, it is just a series of messages like "note on," "note off," "note/pitch," "pitchbend," and velocity.  I think this would be easy to convert to the physical world.  Note on and Note off are pretty easy to understand, velocity could be the air pressure that we let though the valve (we could PWM a solonoid), i imaging that pitch bending we just ignore.

MIDI note 60 is middle C (C4).

When a key is pressed the keyboard creates a "note on" message.  This message consists of two pieces of information: which key was pressed (called "note") and how fast it was pressed (called "velocity").

"Note" describes the pitch of the pressed key with a value between 0 and 127.  I've copied the table in fig 2 from NYU's website, it lists all the MIDI notes and their standard musical notation equivalents.  You can see that MIDI note 60 is middle C (C4).

"Velocity" is a number between 0 and 127 that is usually used to describe the volume (gain) of a MIDI note (higher velocity = louder).  Sometimes different velocities also create different timbres in an instrument; for example, a MIDI flute may sound more frictional at a higher velocity (as if someone was blowing into it strongly), and more sinusoidal/cleaner sounding at lower velocities.  Higher velocity may also shorten the attack of a MIDI instrument.  Attack is a measurement of how long it takes for a sound to go from zero to maximum loudness.  For example, a violin playing quick, staccato notes has a must faster attack than longer, sustained notes.
something to remember- not all keyboards are velocity sensitive, if you hear no difference in the sound produced by a keyboard no matter how hard you hit the keys, then you are not sending variable velocity information from that instrument.  Computer keyboards are not velocity sensitive, if you are using your computer's keys to play notes into a software sequencer, all the notes will have the same velocity.

When a key is released the keyboard creates another MIDI message, a "note off" message.  These messages also contain "note" information to ensure that it is signalling the end of the right MIDI note.  This way if you are pressing two keys at once and release once of them, the note off message will not signal the end of both notes, only the one you've released.  Sometimes note off messages will also contain velocity information based on how quickly you've released the key.  This may tell a MIDI instrument something about how quickly it should dampen the note.

"Aftertouch" is the force used to press down a key after it has been initially struck, think of it as pressure sensitivity.  Like velocity, aftertouch ranges from 0 to 127.  Aftertouch may be interpreted by a MIDI instrument in a variety of ways; it may affect the volume, timbre, vibrato... you will have to experiment with your own setup to get a feel for what expression you can achieve with aftertouch.  Keep in mind that not all electronic keyboards are capable of producing aftertouch messages and not all MIDI instruments support them.  The MIDI instruments inside GarageBand do not support aftertouch, but many of the MIDI instruments in more sophisticated software like Ableton, Reason, etc, do.  Like velocity, aftertouch messages always have a note associated with them, this means you can send an individual aftertouch message for each of your keys.
Here's a good article on Wikipedia about various types of keyboard expression, including aftertouch and velocity.

You may also have a pitchbend wheel/slider attached to your MIDI keyboard, this will shift the pitch of whatever notes you are currently playing up or down by less than a semitone.  Your pitchbend wheel/slider probably generates pitchbend values from 0-127 (where 64 = no pitchbend), but some high res devices will generate values from 0-16,383 (where 8192 = no pitchbend).  Pitchbend does not have a note associated with it, this means that pitchbend is applied equally to every note you're playing.  Pitchbend, is how we know the difference between an A and an A# or an A flat.

MIDI messages can be sent on 16 different channels as well.  Channels are useful for sending certain notes and messages to one MIDI instrument and other notes/messages to another MIDI instrument.  Usually, separate MIDI channels are used for different sounding instruments to create a multitracked song, channel 0 might be a piano-sounding instruments, and channel 1 could be a guitar sound.  I could set it up to merge all channels into one channel or potentially just set it up to play one specific channel or maybe give the ability to disable specific channels.

Velocity is often set back to 0 when the note off message is sent. This is because a MIDI message with a note on command and velocity 0 is the same as a note off message. Sometimes when a software MIDI environment receives a note off message it will automatically translate it into a note on message with velocity 0 because they are the same. You will probably find that it is easier to program MIDI by sending these note on/velocity=0 messages rather than sending note off.