Para usuarios de macOs 10.14 mojave con Xcode-beta instalado, lo siguiente debería funcionar como xcode-select --install no parece proporcionar los archivos de encabezado que faltan, al menos no en una ubicación que funcione para instalar python a través de brew...
Lo que funcionó para mí es lo siguiente:
brew install zlib
brew link zlib --force
#python 3
brew (re)install python3
brew postinstall python3
brew link python3 #just in case...
#python 2
brew (re)install python2
brew link python2 #just in case...
En mi caso también tuve que reinstalar algunos de mis módulos de python previamente instalados a través de pip.
Este es un problema con xcode que no instala zlib correctamente.
Instale la CLI de xcode con:
xcode-select --install
Luego, antes de reinstalar Python con brew, compruebo si el encabezado zlib está donde brew lo está buscando a través de la terminal:
ls /usr/include/zlib.h
Luego reinstale python a través de brew:
brew reinstall python