Lo que sé me ocurre es que ejecutes algún comando del sistema que haga esto. Me explayo un poco:
Primero el servidor tiene que ser tuyo, así puedes instalar lo que necesites y no tengas problemas con las funciones de PHP para ejecutar programas externos por ejemplo
exec().
Segundo cuando subes el video lo guardas en alguna hubicación para luego poder ejecutar el comando con la ruta a dicho archivo (también puedes trabajar con el archivo temporal de este -
creo -).
Despues de lo que dije solo queda buscar que aplicación hace ese trabajo de AVI a FLV no conozco ninguna pero debe existir alguna.
Supongo que hacer todo esto debe ser más facil si el servidor es GNU/Linux o por lo menos yo preferiría que así lo sea.
Cualquier duda me avisas.
Saludos.
PD: Me intereso la idea, mañana busco algo de info y si encuentro algo que sirva vengo y lo posteo... de la misma manera te invito a que postees lo que vayas encontrando.