E: unable to locate package pip

The package you want is not called pip, the name depends on the python version.

Python 2: sudo apt-get install python-pip

Python 3: sudo apt install python3-pip

To install pip, download get-pip.py. Then run this command:

sudo python get-pip.py

It will download and install pip from the source. To check if pip is installed, type this:

which pip

it will show where pip is located

/usr/local/bin/pip

or just type:

pip

In Ubuntu, pip is provided by the python-pip package. You can install it in the Software Center, or, if you prefer to use the command line:

sudo apt-get update && sudo apt-get install python-pip

If you have not already installed python-dev and build-essential, you should install them too. (But it seems your apt-get command might have successfully installed them. If you're not sure, you can check by trying to install them again. Or with apt-cache policy python-dev build-essential.)

Once the necessary software is installed, if you wish to update it further, you can do so with pip itself, by running:

sudo pip install --upgrade pip 
sudo pip install --upgrade virtualenv

Source: How to install pip on Ubuntu by Eliot (dated, but should still apply).