Hej,
there was an AVR awarded design that was making full teletext (thus 40x25 char screens) on composite b&w using only the atmega8. I cannot find the link, but the whole thing was open source.
BTW I am also interested in this project, keep us posted with your experiments, I will try to look for those files in my old hard-drive.
/David