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.
Wow - I'm only 99.9% sure but no, no I really don't believe you can.
That said it might be worth asking on SO.