Problems installing Postgis extension on Ubuntu 14.04

I have Ubuntu 14.04 with Postgres 9.3 and I'm trying to install Postgis extension. One of the most recommended and straightforward ways I found is very simple:

sudo apt-get install postgresql-contrib postgis postgresql-9.3-postgis-2.1

However, this throws an "unmet dependencies" error:

Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:
The following packages have unmet dependencies.

postgis : Depends: libgdal1h (>= 1.9.0) but it is not installable
    Depends: libgeos-c1 (>= 3.4.2) but it is not going to be installed
    Depends: liblwgeom-2.1.3 (>= 2.0.0) but it is not going to be installed

postgresql-9.3-postgis-2.1 : Depends: libgdal1h (>= 1.9.0) but it is not installable
    Depends: libgeos-c1 (>= 3.4.2) but it is not going to be installed
    Depends: liblwgeom-2.1.3 (>= 2.1.2) but it is not going to be installed
    Depends: libproj0 (>= 4.8.0-1) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

I've seen quite a few people having this issue, but haven't found a good solution yet.

The closest question/answer to this that I found so far is this one, however it deals with Ubuntu 12.04, so I feel my question is not a duplicate.

As we can see here all the required packages are rightly updated in the official repository.
To solve the problem you can find a good start point here.

StackExchange Database Administrators Q#72863, answer score: 3