Tiny C Compiler runs decently natively on the kindle 3.
Find it on the mobileread forums compiled for native use.
Code sourcery toolchain works for simple comilation via "arm-none-linux-gnueabi-gcc foo.c" IIRC with no effort. creating native arms. Crosstools-ng as well but neither natively AIUI.
I looked into http://buildroot.uclibc.org/downloads/manual/manual.html#_about_buildroot
for a more comprehensive solution.
There are some options in there for what you require IIRC using x-compile to make the compiler but Crosstools is the more robust chain I had trouble with codesourcery doing true static build. HTH