configure: error: no acceptable C compiler found in $PATH

Question

So I'm trying to install ruby but when I run rbenv install -v 2.2.3 I get the following error:

/tmp/ruby-build.20161217084514.23075 ~
Downloading ruby-2.2.3.tar.bz2...
-> https://cache.ruby-lang.org/pub/ruby/2.2/ruby-2.2.3.tar.bz2
/tmp/ruby-build.20161217084514.23075/ruby-2.2.3 /tmp/ruby-build.20161217084514.23075 ~
Installing ruby-2.2.3...
config.guess already exists
config.sub already exists
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking target system type... x86_64-pc-linux-gnu
checking for gcc... no
checking for cc... no
checking for cl.exe... no
configure: error: in `/tmp/ruby-build.20161217084514.23075/ruby-2.2.3':
configure: error: no acceptable C compiler found in $PATH
See `config.log' for more details

BUILD FAILED (Ubuntu 14.04 using ruby-build 20161121-14-gd799bdd)

Inspect or clean up the working tree at /tmp/ruby-build.20161217084514.23075
Results logged to /tmp/ruby-build.20161217084514.23075.log

Last 10 log lines:
config.sub already exists
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking target system type... x86_64-pc-linux-gnu
checking for gcc... no
checking for cc... no
checking for cl.exe... no
configure: error: in `/tmp/ruby-build.20161217084514.23075/ruby-2.2.3':
configure: error: no acceptable C compiler found in $PATH
See `config.log' for more details

I'm not an expert but it looks like gcc might be missing I try installing gcc via sudo apt-get install gcc and I get the following error:

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
E: Sub-process /usr/bin/dpkg returned an error code (1)

Here's what I've tried:

sudo apt-get install build-essential

then

sudo dpkg --purge gcc
sudo apt-get clean
sudo apt-get -f install

But none of these worked. I think it might even be permission related, I recently had to restore /var/ and have had quite a few unrelated permissions/ownership errors since then. Any idea what's causing this?

EDIT:

When I run update-alternatives --query cc I get the following result:

update-alternatives: error: no alternatives for cc

When I run ls -l /usr/bin/{cc,gcc} here's what I get:

ls: cannot access /usr/bin/cc: No such file or directory
lrwxrwxrwx 1 root root 7 Apr  7  2014 /usr/bin/gcc -> gcc-4.8

Running ls -ld /var/lib/dpkg/alternatives/{,cc} gives me:

ls: cannot access /var/lib/dpkg/alternatives/cc: No such file or directory
drwxrwxr-x 2 mre mre 4096 Dec 17 00:06 /var/lib/dpkg/alternatives/

From running sudo apt-get install --reinstall gcc-4.8 gcc I got:

Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 upgraded, 0 newly installed, 2 reinstalled, 0 to remove and 0 not upgraded.
1 not fully installed or removed.
Need to get 0 B/5,047 kB of archives.
After this operation, 0 B of additional disk space will be used.
E: Internal Error, No file name for gcc:amd64

Then I found this answer and it worked so now gcc is compiling but when I run rbenv install -v 2.2.3 I get this:

Last 10 log lines:
config.guess already exists
config.sub already exists
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking target system type... x86_64-pc-linux-gnu
checking for gcc... gcc
checking whether the C compiler works... no
configure: error: in `/tmp/ruby-build.20161217125354.10629/ruby-2.2.3':
configure: error: C compiler cannot create executables
See `config.log' for more details