Is it possible to run a binary from EEPROM?
Short answer: No; From the atmega328's data sheet (though it applies to all AVR's): 


  AVR uses a Harvard architecture – with
  separate memories and buses for program and data. Instructions in the program memory are
  executed with a single level pipelining. While one instruction is being executed, the next instruction is pre-fetched from the program memory
  
  ...
  
  Program Flash memory space is divided in two sections, the Boot Program section and the
  Application Program section. Both sections have dedicated Lock bits for write and read/write
  protection. The SPM instruction that writes into the Application Flash memory section must
  reside in the Boot Program section


It's architecture prevents using external program memory, but you can load anything into program memory at boot. At that point I would venture to say you are just programming AVR and not arduino, since you would need to replace the arduino bootloader and break the arduino IDE's ability to upload programs.

Alternately you could also use an emulator or interpreter of some intermediate language; basically code that steps through and runs other code. As a general rule an emulator runs around 8x slower. 

There are micro-controllers from other brands that do support this functionality, I know a couple different PIC's do.