O problema era que o zlib e o zlib-devel não estavam instalados antes da instalação. Eu também precisava ter certeza de que o openssl e o openssl-devel estavam instalados e atualizados, porque o PIP falhou em funcionar mais tarde.
Eu colei os comandos e dependências necessários abaixo. Isso foi no Redhat 4.8.5.
yum install gcc
yum install zlib
yum install zlib-devel
yum install openssl
yum install openssl-devel
cd /usr/src
wget https://www.python.org/ftp/python/3.6.1/Python-3.6.1.tgz
tar xzf Python-3.6.1.tgz
cd Python-3.6.1/
./configure
make
make altinstall