GCC, ironically enough, is built by itself - that is to say, you have
to have GCC, in order to build GCC. Ever since the first GCC was built
with binutils (I think it was binutils - anyone around when the first
GCC was built, was it compiled with binutils or the 'cc' on a unix
box?), the previous version of GCC builds the next version, and so on.
So without a C compiler, you'll never be able to build GCC from source.
Anyways, skipping the history lesson, google is your friend.
It looks like fedora 9 ships with GCC 4.3 by default. What output did
your 'yum' commands give you? Do a 'locate gcc | grep bin' or 'find /
-name gcc', and one of those will definitely give you the location of
GCC if you actually have it. If those turn up a gcc binary somewhere,
then it's just an issue of setting your PATH to include that directory
('which' only looks inside of the $PATH environment variable, so if your
path is screwy, it'll break). If you indeed don't have gcc installed,
and yum (for whatever reason) refuses to work, you'll have to download a
binary gcc version from rpmfind.net. Just search for 'gcc' and install
what comes up for your version with 'rpm -ihv (rpm filenames)'. That
should get you up and running.
(FWIW, on a personal note, Fedora sucks balls. Ditch it for a real
distro like one of the Ubuntu flavors, and you'll be free of the
nightmare of RPM hunting.)