Android - How can I compile native applications on my rooted phone?

I can't understand why I have to pay $3 for C4droid as it's just GCC with an editor.

Use the new free CppDroid - C/C++ IDE on Android. It has a lot of included C/C++ examples and tutorials. Blog link, Google Play link (needs 190 MB).

Compiling applications does not take considerable processing power in general. I did it on my 286 all the time. The OP wants gcc on his phone.

Look for C4droid (C/C++ compiler) in the Google Market. Then install the GCC plugin for C4droid from the market. (These do cost a couple of dollars).

From the market description:

It's a plugin for c4droid, that allows it to compile C and C++ source code using GCC. It contains gcc 4.7 with Bionic (Android libc). Source code hadn't been modified, so you can compile it yourself, if you want.

You can write, compile and distribute native code as an Android Application.

Look here for more info about the NDK.

If you want it done without the official framework and application packaging then you'll need to look into cross-compiling the application for the ARM architecture.