I heard about the chicken and the egg and bootstrapping. I have a few questions.
What wrote the first compiler that converted something into binary instructions?
Is assembly compiled or translated into binary instructions?
...I'd find it hard to believe they wrote a compiler in binary.
The first programs were written in machine code (not assembly language) - actual numbers plugged into the computer memory using switches. We've come a long way...
Sometimes this still happens to a small extent - to patch small bits of code or create thunks. I recall punching in numbers into Basic strings that were then executed as small, fast subroutines on early micros. I also remember toggling switches on a PDP-11's front panel to enter a bootloader program into its memory for a university course.
These programs would sometimes be used to process text files to create other programs, and voila programming languages were created.
Please read about compiler bootstrapping and the history of compiler writing
The idea is to write a very simple compiler directly in machine code, use it to write a more sophisticated compiler, use the second one to build a third one and so on until you can have a full featured compiler.
Assembly instructions are (generally) a direct mapping to opcodes, which are (multi-)byte values of machine code that can be directly interpreted by the processor. It is quite possible to write a program in opcodes directly by looking them up from a table (such as this one for the 6039 microprocessor, for example) that lists them with the matching assembly instructions, and hand-determining memory addresses/offsets for things like jumps.
The first programs were done in exactly this fashion - hand-written opcodes.
However, most of the time it's simpler to use an assembler to "compile" assembly code, which automatically does these opcode lookups, as well as being helpful in computing addresses/offsets for named jump labels, et cetera.
The first assemblers were written by hand. Those assemblers could then be used to assemble more complicated assemblers, which could then be use to assemble compilers written for higher-level languages, and so on. This process of iteratively writing the tools to simplify the creation of the next set of tools is called (as mentioned by David Rabinowitz in his answer) bootstrapping.
What wrote the first compiler that converted something into binary instructions?
A human did. Read about the A-0 system A-0 system:
In 1952, Grace completed her first compiler for Sperry, known as the A-0. The A-0 System was a set of instructions that could translate symbolic mathematical code into machine language. In producing A-0, she took all the subroutines she had been collecting over the years and put them on tape. Each routine was given a call number, so that it the machine could find it on the tape. "All I had to do was to write down a set of call numbers, let the computer find them on the tape, bring them over and do the additions. This was the first compiler," as described by Grace.
Woz said in one of his public talks that when he started, he couldn't afford a compiler so he compiled to binary by hand on paper. If you want to see something even more wild, read about the conditions under which Bill Gates and Paul Allen wrote the BASIC for the Altair 8800.
Regarding "writing a computer in binary" -- take a step back from being a programmer and think about what the early computers were. High level stuff didn't yet exist -- you thought about everything in the low level because that's all it was. You had hardware that could do basic logic and arithmetic that you manipulate via machine code (which is just compiled assembly -- Amber explains why this part isn't hard to do by hand) and you wanted this hardware to perform certain mathematical feats. You didn't worry about the non-existent operating system, you just told the hardware (in assembly) how to manipulate the numbers you feed it. It was a just big calculator. The computer of today was built one abstraction at a time.
If you want to break down the barrier that keeps computers feeling like magic, I HIGHLY recommend reading CODE by Charles Petzold and/or The Elements of Computing Systems. With just a basic knowledge of programming, these wonderfully accessible books will have you understanding computers from top to bottom. Obviously, one can't get a comp. sci. or EE degree after just 2 books, but I can say as a self-taught programmer who missed out on the formal training: these books rocked my world!