apt - Dependency problems after faulty Ubuntu upgrade ( `gcc-5-base` )

I tried upgrading from 14.02 to the newest available version.
I package froze the installation progress and I was left with a broken system. Many important packages ( including all of the apt packages ) where depending on a broken libc6 and libstdc++. After trying to manually reinstalling and recompiling all the libraries depending on those packages have I ended up in the following dependencies hell.
# dpkg --configure -a

dpkg: error processing package click (--configure):
 subprocess installed post-installation script was interrupted
dpkg: dependency problems prevent configuration of libstdc++6:amd64:
 libstdc++6:amd64 depends on gcc-5-base (= 5.3.1-8ubuntu2); however:
  Version of gcc-5-base:amd64 on system is 5.3.0-3ubuntu1~14.04.
dpkg: error processing package libstdc++6:amd64 (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of libstdc++6:i386:
 libstdc++6:i386 depends on gcc-5-base (= 5.3.1-8ubuntu2); however:
  Version of gcc-5-base:i386 on system is 5.3.0-3ubuntu1~14.04.
dpkg: error processing package libstdc++6:i386 (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of ubuntu-system-settings:
 ubuntu-system-settings depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:amd64 is not configured yet.
 ubuntu-system-settings depends on click | ubuntu-snappy-cli; however:
  Package click is not configured yet.
  Package ubuntu-snappy-cli is not installed.
dpkg: error processing package ubuntu-system-settings (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of ubuntu-system-settings-online-accounts:
 ubuntu-system-settings-online-accounts depends on libstdc++6 (>= 4.1.1); however:
  Package libstdc++6:amd64 is not configured yet.
 ubuntu-system-settings-online-accounts depends on ubuntu-system-settings; however:
  Package ubuntu-system-settings is not configured yet.
dpkg: error processing package ubuntu-system-settings-online-accounts (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of apt-transport-https:
 apt-transport-https depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:amd64 is not configured yet.
dpkg: error processing package apt-transport-https (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of apt-utils:
 apt-utils depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:amd64 is not configured yet.
dpkg: error processing package apt-utils (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of libapt-inst1.7:amd64:
 libapt-inst1.7:amd64 depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:amd64 is not configured yet.
dpkg: error processing package libapt-inst1.7:amd64 (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of libapt-pkg4.16:amd64:
 libapt-pkg4.16:amd64 depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:amd64 is not configured yet.
dpkg: error processing package libapt-pkg4.16:amd64 (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of libapt-pkg4.16:i386:
 libapt-pkg4.16:i386 depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:i386 is not configured yet.
dpkg: error processing package libapt-pkg4.16:i386 (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of apt:
 apt depends on libapt-pkg4.16 (>= 1.0.10.2ubuntu1); however:
  Package libapt-pkg4.16:amd64 is not configured yet.
 apt depends on libstdc++6 (>= 5.2); however:
  Package libstdc++6:amd64 is not configured yet.
dpkg: error processing package apt (--configure):
 dependency problems - leaving unconfigured
resolvconf: Error: /run/resolvconf/interface either does not exist or is not a directory
dpkg: error processing package resolvconf (--configure):
 subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
 click
 libstdc++6:amd64
 libstdc++6:i386
 ubuntu-system-settings
 ubuntu-system-settings-online-accounts
 apt-transport-https
 apt-utils
 libapt-inst1.7:amd64
 libapt-pkg4.16:amd64
 libapt-pkg4.16:i386
 apt
 resolvconf

# apt-get -f upgrade

Reading package lists...
Building dependency tree...
Reading state information...
Correcting dependencies... failed.
The following packages have unmet dependencies:
 libapt-inst1.5 : Depends: libapt-pkg4.12 (>= 0.8.16~exp9) but it is not installable
 libstdc++6 : Depends: gcc-5-base (= 5.3.1-8ubuntu2) but 5.3.0-3ubuntu1~14.04 is installed
 libstdc++6:i386 : Depends: gcc-5-base:i386 (= 5.3.1-8ubuntu2) but 5.3.0-3ubuntu1~14.04 is installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.
E: Unable to correct dependencies

Now I tried to update from gcc-5-base 5.3.0 to 5.3.1 but then I end up with a lot of broken dependencies for these packages:

Reading package lists...
Building dependency tree...
Reading state information...
Correcting dependencies... failed.
The following packages have unmet dependencies:
 lib32gcc1 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 lib32stdc++6 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libapt-inst1.5 : Depends: libapt-pkg4.12 (>= 0.8.16~exp9) but it is not installable
 libatomic1 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libcilkrts5 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libgcc1 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libgcc1:i386 : Depends: gcc-5-base:i386 (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libgfortran3 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libgomp1 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libitm1 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 liblsan0 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libquadmath0 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libtsan0 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed
 libubsan0 : Depends: gcc-5-base (= 5.3.0-3ubuntu1~14.04) but 5.3.1-8ubuntu2 is installed