Sí es posible, pero probablemente te va a tomar mucho tiempo dependiendo de la complejidad de la escena.
Busca en internet "rotoscoping"
https://www.google.com.mx/search?q=rotoscoping
Eso lo utilizas ahora como una máscara para cambiar el fondo.
Lo que te dice francisco es un chroma key. O sea sacar tu video con una pantalla azul o verde de fondo.
https://www.google.com.mx/search?q=chroma+key