Hello
I've coded exactly what you're looking for : http://olb7.free.fr/arduino/syncInterrupt.pde
640 * 480 @ 60Hz - FvSync = 60.3 Hz / FhSync = 31.3 kHz
HSync : pin 7 Arduino, pin 13 VGA
VSync : pin 6 Arduino, pin 14 VGA
Arduino's pin 5 is HIGH when video can be sent, LOW otherwise. I use it to power a transistor.
The sync routine is trigged by Timer2. You could achieve a slightly faster sync (31.5kHz) by using Timer1 instead. But it works well !
Keep us posted !