Estate atento ya que en esta reseña encontrarás el arreglo que buscas.
Si bien no resuelve su problema directamente, debería poder instalar la biblioteca utilizando el excelente repositorio binario no oficial de Windows aquí:
http://www.lfd.uci.edu/~gohlke/pythonlibs/#python-levenshtein
Descargar el .whl archivo e instalarlo usando pip:
pip install python_Levenshtein-0.12.0-cp35-none-win_amd64.whl
En cuanto al error, estoy de acuerdo con Rogalski. Es probable que necesite un compilador de C instalado (como la edición gratuita de Visual Studio Community).
Editar: Lo siento, acabo de darme cuenta de que esto ya se sugirió en una de sus preguntas vinculadas aquí: https://stackoverflow.com/a/29926192/6345502 – ¡Espero que ayude de todos modos!
Tuve un problema similar, resuelto instalando otra biblioteca relacionada: python-Levenshtein-wheels;
pip install python-Levenshtein-wheels
En caso de que esté utilizando Anaconda, intente:
conda install -c conda-forge python-levenshtein