Primeiro, locale -a | grep ru_RU
nunca retornará o que você escreve. Talvez locale -a | grep ru_UA
.
Em segundo lugar, você pode gerar novos locais emitindo:
sudo locale-gen ru_UA.KOI8-R
Eu não verifiquei se ru_UA.KOI8-R
é a forma exata para o que você deseja.
Mais sobre: (Re-) Gerando localidades .