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 .