How to compile GCC for android?

The Android NDK already includes the complete GNU toolchain which runs on your computer. You should be able to use it to compile native versions of whatever program you want.

In the NDK, see docs/STANDALONE-TOOLCHAIN.html for setting up the cross-compiler. You probably want to follow the steps for "Invoking the compiler (the easy way)" to set up a copy of the toolchain which you should be able to use with configure scripts commonly included with GNU applications (like gcc).

This really is a non-trivial task and I recommend you read the docs very carefully. It also contains various values for CFLAGS, LDFLAGS etc. that you will need to customize and use when configuring and compiling your programs.

As for compiling gcc, make, etc., themselves, it's probably not necessary or desirable to do so. gcc, for instance, is going to be huge and you may not have enough storage on the phone to install it. If your ultimate intention is to compile some program to run natively on the Android device, then I would recommend you just use the NDK and point the app's configure script at it.