yes the sanguino(ATMega644p) would work well, however do note that it would require a quick modification the the library. This is because the OC1A pin is not on PORTB1, it is on PORTD5, the required modifications would be setting PORTD5 to be output, and connect the sync resistor to that pin (i don't know what it is on the sanguino).
The arduino mega would be even better resolution wise as it has 8k sram.
As far as the best DIP chip to use the ATMega1284p would be best, if it can be found. it is the bigger brother to the 644, with 16k sram! (@20mhz 320x240 would be possible)
clock speed really isn't an issue with this frame buffer method because unless we have about 8k of SRAM 16mhz is fast enough to output the buffer.