Is it possible to compile a full Linux system with Intel's compiler instead of GCC?

You won't be able to compile everything with icc. Many programs out there use GCC extensions to the C language. However Intel have made a lot of effort to support most of these extensions; for example, recent versions of icc can compile the Linux kernel.

Gentoo is indeed your best bet if you like recompiling your software in an unusual way. The icc page on the Gentoo wiki describes the main hurdles.

First make a basic Gentoo installation, and emerge icc. Don't remove icc later as long as you have any binary compiled with icc on your system. Note that icc is installed in /opt; if that isn't on your root partition, you'll need to copy the icc libraries to your root partition if any of the programs used at boot time are compiled with icc.

Set up /etc/portage/bashrc and declare your favorite compilation options; see the Gentoo wiki for a more thorough script which supports building different packages with different compilers (this is necessary because icc breaks some packages).

export OCC="icc" CFLAGS="-O2 -gcc"
export OCXX="icpc" CXXFLAGS="$CFLAGS"
export CC_FOR_BUILD="${OCC}"

It would certainly be an interesting experience. Recompiling an entire Linux distro using an alternative compiler would not really be straightforward however. Many essential packages depend on GCC and other GNU toolchain utilities.

It would be feasible to use an alternative compiler for those packages that don't require GCC to create a hybrid. It might be possible to replace GCC-dependent packages with others that would build with your compiler, but in most cases there aren't too many alternatives. Where there are, you'll have to determine whether those alternatives will be as functional for your intended use.

The real question though is: would it be worth it? If you are trying to build an embedded system, an alternative compiler might produce smaller binaries. If you are building a compute cluster, you may get faster code execution. If you are building a desktop, you'll get a great learning experience.

I think in the end (assuming you are building a desktop) you'll find to be true what many source distro users eventually decide: the amount of time spent optimizing and building and rebuilding far outweighs the time saved by faster code execution. That is not to say that it shouldn't be done -- it could be quite fun. If you do it, this site would be a great place to find answers and document your efforts.