Se o comando update-locale não estiver disponível, seu sistema está gravemente corrompido. Talvez a variável PATH não contenha todos os diretórios que deveria.
De qualquer forma, não há motivo para alterar a propriedade de /etc/default/locale . Tente isto:
sudo /usr/sbin/update-locale LANG=en_US.UTF-8