I was setting up pytorch fork in a new conda env and run into te same issue.
I had gcc-4.9 already installed. What worked for me was
conda create --name pytorch-dev python=3.6
source activate pytorch-dev


export CMAKE_PREFIX_PATH="$(dirname $(which conda))/../" # [anaconda root directory]

# Install basic dependencies
conda install numpy pyyaml mkl setuptools cmake cffi

# Add LAPACK support for the GPU
conda install -c soumith magma-cuda80 # or magma-cuda75 if CUDA 7.5


export CMAKE_C_COMPILER=/usr/bin/gcc-4.9
export CMAKE_CXX_COMPILER=/usr/bin/gcc-4.9

NO_CUDA=1 DEBUG=1 python setup.py clean
NO_CUDA=1 DEBUG=1 python setup.py build develop

This works. I was not attempting to perform full installation with CUDA and DEBUG=0 yet
Edit This workaround works with CUDA and no DEBUG as well