E' possibile, se puoi metter mano al server (hosting dedicato) o se il servizio hosting ti permette di utilizzare ffmpeg (ad esempio, ma suppongo ci siano anche altri tool analoghi). Con ffmpeg puoi convertire da avi a flv (googla): il tuo script dovrebbe chiamarlo da shell (con exec via php) pasandogli i giusti parametri.