Primeiro, reinstalar o mysql não é uma solução real. Especialmente se você quer dizer remover e instalar os pacotes - isso não afetará os arquivos em seu diretório de dados e seu problema não mudará.
Em segundo lugar, você nunca deve ter que tocar em arquivos binlog no disco - excluí-los do sistema de arquivos não é o caminho certo para gerenciá-los. Existem comandos no mysql que removerão logs antigos. O MySQL também deve manter o arquivo de índice, de modo que os arquivos no disco correspondam à lista de binlogs existentes que ele mantém. Consulte Limpar registros bináriosEntão a bagunça em que você está é porque você está fazendo suposições e tocando em arquivos que não deveria.
Este erro:
/usr/sbin/mysqld: File '/etc/mysql/var/log-bin.index' not found (Errcode: 13)
Não significa que não esteja lá; Erro 13 significa "Permissão negada" O que provavelmente significa que o mysql não pode gravar em /etc/mysql/var/
Tudo o que você precisa fazer agora é corrigir as permissões em /etc/mysql/var/
Algo como:
chown mysql:mysql /etc/mysql/var; chmod 0775 /etc/mysql/var
Se não houver um arquivo .index e nenhum binlogs, o mysql iniciará do zero e criará os arquivos necessários. Remova todos os arquivos desse diretório.