Yay! I'm now able to generate a stable image on the telly. I fixed the odd colors issue (it seems that RGB signals must stay low during the color burst phase normally used in composite video, which doesn't really sound weird, if you think about it), then added vertical sync.
Note that I'm currently rendering a 312 lines non-interlaced screen, instead of a 625 lines interlaced one. A interlaced display would cause too much flickering for a video game (as it would give a 25 Hz total refresh rate).

I made a first test of video output through the SCART connector of my TV. Leaving apart the vertical sync stuff for the moment, I focused on the generation of some RGB signal with horizontal sync.

The main source for information I used is this site.

I wrote a small CPLD design to output red, green and blue, as well as the horizontal sync signal, in order to display vertical stripes of different colors. On this picture you can see the very first attempt : I just had the red and sync signal connected, and it showed up a slowly horizontally scrolling set of vertical red stripes (which were in fact fading in and out to black). Nothing very fancy, but still a great moment of satisfaction. :)

I discovered that the reason why it seems to scroll was because the TV didn't care about my sync signal, as I was outputting 5V only to pin 8 of the SCART connector, which wasn't enough to select composite sync. So I took the voltage for this pin directly from the output of the PSU (set to 9V, but actually outputting more than 10V), and got a stable image, but with odd colors... I think I know the reason for this, and I will hopefully solve this issue, and add vertical sync in a few.

I bought a cheap SCART cable some days ago. And as you can see on this picture, I soldered the pins I need to some wires that I will plug into my breadboard.
Now I will try to generate a proper video signal using a CPLD.

Nothing much more to say... As you can see on this picture, I have made something cleaner, by using a small DIL socket plugged in the breadboard.

With the XC9752 CPLDs I just have received, I protoyped a minimal system on a breadboard : Power supply and voltage regulator, clock circuit, programming port, and a LED. After a while, I successfully programmed the CPLD with the "EE Hello World" : a blinking LED.
Great. Now I will try to make something cleaner, then make some experiments on video output on TV. Stay tuned :)