I wrote an actual libc-free "Hello World" program for Linux: http://codepad.org/rUckf7jR

It should work as 32-bit or 64-bit and compile with clang or gcc. It compiles to about 11 assembly instructions.

To produce a fairly small file:

    $ clang -nostdlib -O3 -o helloworld -m32 helloworld.c
    $ strip helloworld
    $ strip -R .note.gnu.build-id ./helloworld
    $ wc -c helloworld
    428 helloworld