I hate to suggest another micro but have you guys checked out the propeller chip?
It is cheap and has video capabilities. You could load up the VT100 emulator on the propeller and send it serial commands to display text.
I think real graphics will be tough because the little atmel doesn't have enough memory to fill a real graphics buffer.
It would make a really cheap video shield.