Bueno, en primer lugar hay que afirmar que definitivamente si es posible. A nivel conceptual puedo decirte que es algo tan simple como procesar cada frame del video original, escribir el sub-título correspondiente a ese frame y almacenarlo en el nuevo video.
Detalles de la forma de conseguir esto, pues dependen del formato en que esté almacenado el video (siendo el mas fácil de trabajar, a mi entender, un AVI de windows).
Mi recomendación es que comences por definir los formatos de video que queres trabajar, luego que busques información sobre su estructura interna y los algoritmos de compresión/descompresión para obtener cada frame como una imagen que pueda procesarse.
Además, una lectura rápida sobre la clase TCanvas, con la que se haría la "escritura" en cada frame (via TextOut).
Es una orientación general. A medida que profundices en la comprensión y el desarrollo de tu programa (proyecto ambicioso, eh) no dudo que contarás con un buen apoyo en estos foros.
Hasta luego.