Its much more precise using ASM or C but you can generate a valid video signal using arduino. The PAL standard for example allows +-0.3 microseconds for its timing pulses. By using some asm nops you can tune your code to work ok. The main problem people seem to be having is they aren't generating proper signals....not using eq pulses and field sync pulses for example in their code. Also it is important to disable the interrupts. If you get hold of the specifications for TV signals, and follow them, you can generate something that will work ok on most modern tv's.
If you don't have an oscilloscope then you can use a timing trick mentioned in this thread http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1174587934/10#10
to measure timing precisely. I'm gonna get hold of a DSO in a few weeks and I'll write a better video gen example then.