how to add video title without re-encoding the video
It depends a bit on your file format. But it is possible; if you create a title as a separate video you can concatenate (join) the title and the original video usng tools such as ffmpeg. Generally this will work best if they are the same codec with the same settings. For concatenation using ffmpeg see the FAQ. 

Some formats, like MPEG2 program streams (like you get on DVDs) can actually be concatenated by simply adding the second file to the end of the first, eg. by using cat file1.mpg file2.mpg &gt; newfile.mpg on the command line.