196
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.
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!