Unable to install anything using apt

I was trying to install an earlier gcc and g++ (4.6.3) for compatibility reasons and now apt seems to be broken. It appears that apt-get install behaves like this for everything, not just dpkg:

>> sudo apt-get install dpkg 
Reading package lists..
Done 
Building dependency tree
Reading state information... 
Done 
dpkg is already the newest version. 0 upgraded, 0 newly installed, 0 to   
remove and 0 not upgraded. 1 not fully installed or removed. After this
operation, 0 B of additional disk space will be used. Do you want to
continue? [Y/n]

And choosing "Y" always results in this:

Setting up gcc (4:4.8.2-1ubuntu6) ...
update-alternatives: error: alternative path /usr/bin/gcc doesn't exist
dpkg: error processing package gcc (--configure):
subprocess installed post-installation script returned error exit status 2
E: Sub-process /usr/bin/dpkg returned an error code (1)

I did run the configure script while trying to install gcc 4.6.3 and I might have given a bad value for the --target option. I have tried various combinations of the following without success:

apt-get update && apt-get upgrade
apt-get install -f
sudo dpkg --configure -a
apt-get remove/purge/autoremove gcc

Also, Synaptic claims there are no broken packages.

Advice is appreciated.

EDIT: In response to comments

>> sudo apt-get purge gcc
[sudo] password for user: 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be REMOVED:
  gcc*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 42.0 kB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 278757 files and directories currently installed.)
Removing gcc (4:4.8.2-1ubuntu6) ...
Processing triggers for man-db (2.6.7.1-1ubuntu1) ...

>> sudo dpkg -C
The following packages are only half configured, probably due to problems
configuring them the first time.  The configuration should be retried using
dpkg --configure <package> or the configure menu option in dselect:
 gcc                  GNU C compiler

Trying to remove any of these fails with complaints about dependencies:

>> sudo dpkg --get-selections | grep gcc
gcc                     install
gcc-4.6                     install
gcc-4.6-base:amd64              install
gcc-4.8                     install
gcc-4.8-base:amd64              install
gcc-4.9-base:amd64              install
libgcc-4.8-dev:amd64                install
libgcc1:amd64                   install

>> sudo dpkg --configure -a
Setting up gcc (4:4.8.2-1ubuntu6) ...
update-alternatives: error: alternative path /usr/bin/gcc doesn't exist
dpkg: error processing package gcc (--configure):
 subprocess installed post-installation script returned error exit status 2
Errors were encountered while processing:
 gcc

>> sudo dpkg -P gcc-4.9-base gcc-4.8-base gcc-4.8 1> command.out
dpkg: dependency problems prevent removal of gcc-4.9-base:amd64:
 libgcc1:amd64 depends on gcc-4.9-base (= 4.9.1-0ubuntu1).

dpkg: error processing package gcc-4.9-base:amd64 (--purge):
 dependency problems - not removing
dpkg: dependency problems prevent removal of gcc-4.8-base:amd64:
 libitm1:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libgomp1:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libstdc++6:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libgfortran3:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libasan0:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libgcc-4.8-dev:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libtsan0:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libquadmath0:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libstdc++-4.8-dev:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 cpp-4.8 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).
 libatomic1:amd64 depends on gcc-4.8-base (= 4.8.2-19ubuntu1).

dpkg: error processing package gcc-4.8-base:amd64 (--purge):
 dependency problems - not removing
dpkg: warning: ignoring request to remove gcc-4.8 which isn't installed
Errors were encountered while processing:
 gcc-4.9-base:amd64
 gcc-4.8-base:amd64

>> sudo dpkg -P gcc-4.6 gcc-4.6-base
dpkg: dependency problems prevent removal of gcc-4.6:
 g++-4.6 depends on gcc-4.6 (= 4.6.4-6ubuntu2).

dpkg: error processing package gcc-4.6 (--purge):
 dependency problems - not removing
dpkg: dependency problems prevent removal of gcc-4.6-base:amd64:
 gcc-4.6 depends on gcc-4.6-base (= 4.6.4-6ubuntu2).
 libstdc++6-4.6-dev depends on gcc-4.6-base (= 4.6.4-6ubuntu2).
 g++-4.6 depends on gcc-4.6-base (= 4.6.4-6ubuntu2).
 cpp-4.6 depends on gcc-4.6-base (= 4.6.4-6ubuntu2).

dpkg: error processing package gcc-4.6-base:amd64 (--purge):
 dependency problems - not removing
Errors were encountered while processing:
 gcc-4.6
 gcc-4.6-base:amd64