Heh, funny, I had nearly the exact same issue yesterday
The company I work for has been developing it's own version of Linux... one that runs on Windows (called LOW, Linux On Windows). At it's heart, it's a slim and trim Debian install. Does not come with GCC (or many other things, 35 MB download) so I had to install it. I found the best, and easiest way, to install it was to use your version of Linux's package installer. RPM's for redhad, .deb for debian, etc... makes the install quite easy.
To install GCC (3.3.2.) you kinda already need a compiler, because it comes only as binaries needing to use the configure - make install method (at least the version I found)
Took me a good 3-4 hours to finally get the stupid thing working. Good luck