FFmpeg (wiki) is one option; you can achieve what you want either with the subtitles filter (see also here) or the drawtext filter.
The subtitles filter requires ffmpeg to be compiled with
--enable-libass and drawtext requires it to be compiled with
--enable-libfreetype. If you're on Linux, the former is fairly likely to be the case, though the latter may not be. Also, beware than Debian and its derivatives (including Ubuntu et al) are using the forked tool avconv, from the libav project (see here for a summary of the situation); some people have reported problems with avconv vs ffmpeg. I would recommend using ffmpeg, mainly because there seem to be more ffmpeg users than avconv users on the SE network, so you'll be able to get better help here.
If the version in your repos is not compiled to do these, you can grab a static build from the FFmpeg website, or you can compile it yourself, following one of the guides on the ffmpeg wiki, making sure to use the correct flags.