I agree with Nigel, an OSD chip is the easiest path to go.
I used a Sanyo device many moons ago, worked very well.
PAL and NTSC are quite similar in essence, they differ in the vertical and horizontal sync timing, the chroma subcarrier frequencies and the fact that PAL alternates the chroma subcarrier phase each line (thus the name). There are other more subtle parameters, like the infamous NTSC black setup. SECAM is a totally different beast altogether.
However, with the OSD chips, they take care of all those issues, all you need to do, is to feed them the text overlay you want to display serially from your microprocessor. A video buffer will also be required at the output if you have to drive 75 ohm loads.