What exactly are you wanting to do with video and audio?
If you want to overlay lo-res information on an existing analog video stream, that can be done. If you want to do any higher processing, or generate higher resolutions, then you want to move to another platform. The overlay can be be done with the Video Experimenter shield:
Lo-res video game graphics can be done with the Gameduino:
However, my sense is that for anything more complex, you want to consider other platforms. Grumpy Mike listed Rasperberry Pi, which is still in limited distribution. My sense is that there currently isn't much for off the shelf software for it. One big problem is the video processing is not open source, and so a lot of the video processing would be slooooow.
You could go with several of the other ARM embedded boards, such as BeagleBone, Simplecortex, Mbed. I don't know much about them.
Another possibility is the Parallex Propeller, which probably is more setup for video processing.
Another possibility is getting a PC in a small form factor to use, instead of an embedded processor.
Android tablets might be another possibility, but I'm not sure how easy is it to add apps to a general tablet.