Ok, managed to get it installed.
Downloaded GZipped tarball:
tar xvf Python-2.7.11.tgz
Then I ran into some trouble installing paho-mqtt for python 2.7.11
This updated my version of pip to the latest
then I could finally properly run:
python2.7 /usr/bin/pip install paho-mqtt
That finally got me all up to date with python 2.7.11 and paho-mqtt.