Because Clojure is built on top of the JVM, I would guess I could use GCJ to compile it directly to machine code, but I can't find any information about it.
When it's possible, how could I then "strip" it to it's bare essentials, so the startup time and memory footprint is as small as possible.
I'd really like to write small terminal programs following the UNIX principles with Clojure
In theory, you could AOT-compile Clojure source code to Java bytecode, and then use gcj to compile this byte code to native machine code. In practice, I would not expect this to work; gcj has severe limitations that prevent its use for most modern Java applications. Specifically, its support for language features stops at Java 1.2 (Clojure requires Java 1.6), and it has incomplete implementations of the standard class libraries required by the Clojure runtime. In the wild, I've seen Clojure applications crash and burn when accidentally launched using the gcj runtime instead of the OpenJDK or Oracle JREs.