Usa un editor no lineal.
Acá hay uno gratis.
http://www.serif.com/free-video-editing-software/
No funcionan todos los formatos de video/resolución.
En ese caso puedes usar un trial de otro, por ejemplo el de Corel Video Studio.
Básicamente pones un video en una pista, y en otra pista pones cualquier otra cosa, por ejemplo un png transparente en el espacio requerido o una herramienta de rectangulito.