O formato do contêiner AVI não suporta legendas incorporadas (muxed) - ele apenas suporta hard subs, o que requer a re-codificação do vídeo com as legendas atualmente em cada quadro de vídeo.
Para ter legendas com mux, você precisa usar os formatos de contêineres MKV ou MP4, dependendo do formato das legendas.
Seus arquivos AVI podem ser remuxados para qualquer um dos contêineres, novamente dependendo dos codecs de áudio e vídeo. Veja Comparação dos formatos de contêiner na Wikipedia para tabelas de compatibilidade.
Eu descobri que o MKV suporta muito mais combinações do que o MP4
O pacote MKVToolNix está disponível para Linux e fará tudo que você precisa
Para o MP4, a ferramenta a ser usada é a MP4Box
Se você precisar de mais informações sobre a diferença entre um formato contêiner (por exemplo, AVI, MP4, MKV etc.) e um codec (por exemplo, DivX, Xvid, H.264 etc.), então O formato de contêiner digital e seus artigos vinculados é um bom lugar para começar.