It is possible (if tedious) to write direct machine code. Maybe you write the program down in assembler on a piece of paper, and then you translate it by hand into the numeric machine code instructions which you enter into the machine memory. You can even skip the assembler-on-paper step if you have memorized the numeric values of all the machine code instructions - not uncommon in those days, believe it or not!
The very first computers were directly programmed in binary by toggling physical switches. It was a great productivity improvement when hardware evolved to let the programmer (or the data entry assistant) enter code in hexdecimal numbers via a keypad!
A software assembler only became relevant when more memory became available (since assembler code takes up more space than raw machine code) and hardware evolved to allow alphanumeric input. So the first assemblers were written directly by people fluent in machine code.
When you have an assembler, you can write a compiler for a higher level language in assembler.
The story for C has multiple steps. The first C compiler was written in B (a predecessor to C) which in turn was written in BCPL. BCPL is a pretty simple language (for example it doesn't have types at all), but still a step up from raw assembler. So you see how gradually more complex languages is build in simpler languages all the way back to assembler. And itself C is a pretty small and simple language by todays standards.
Today, the first compiler for a new language is often written in C, but when the language reaches a certain maturity it is often rewritten "in itself". The first Java compiler was written in C, but later rewritten in Java. The first C# compiler were written in C++, but recently it has been rewritten in C#. The Python compiler/interpreter is written in C, but the PyPy project is an attempt to rewrite it in Python.
But you don't have to use C as the "starting language" for a compiler. The first F# compiler was written in OCaml, which is the other language which is most closely related to F#. When the compiler was complete, it was rewritten in F#. The first compiler for Perl 6 was written in Haskell (a pure functional language very different from Perl) but now has a compiler written in C.
An interesting case is Rust, where the first compiler was written in OCaml (now it is rewritten in Rust). This is notable because OCaml is generally considered higher level than Rust, which is a closer-to-the-metal systems language. So it is not always higher-level languages implemented in lower-level languages, it might also be the other way around.