Is it possible to build gcc without a c compiler already on the machine? If so, how?
What you're talking about is known as bootstrapping a compiler.
Typically this is done by cross-compiling the compiler on another machine for the target architecture. You can find some background here and here. It's not a trivial process, though. If your target isn't architecture that GCC already supports then you've got a lot of work ahead of you.