pcDuino is a mini PC platform that runs a PC like OS such as Ubuntu and Android ICS. It outputs video through a HDMI interface. Moreover, newer versions have hardware headers compatible with Arduino.
All I need to get going is a >8gb Micro SD card for the image, and a 2amp 5v Micro USB power supply. Stay tuned as this project gets off the ground.