pip с релиза 3.6.0 так и не пропатчили. Прописали в него жёстко локаль utf-8, и тем самым поломали установку на неюникодных локалях. С локалью KOI8-R исправляется так:
mkdir fixpip
cd fixpip
unzip ../Lib/ensurepip/_bundled/pip-9.0.1-py2.py3-none-any.whl
sed -i "s/'utf-8'/'koi8-r'/g" pip/_vendor/distro.py
zip -r ready.zip pip pip-9.0.1.dist-info
mv ready.zip ../Lib/ensurepip/_bundled/pip-9.0.1-py2.py3-none-any.whl
cd ..
rm fixpip/ -R