Ha, I've done this. Many CPUs have simple, fixed-size instructions that are just a couple of bytes long. For a simple CPU like a Motorola 6800 for example, you could fit all of its instructions on a single sheet of paper. Each instruction would have a two-byte opcode associated with it, and arguments. You could hand-assemble a program by looking up each instruction's opcode. You'd then write your program on paper, annotating each instruction with its corresponding opcode. Once you had written out your program, you could could burn each opcode in sequence to an EPROM which would then store your program. Wire the EPROM up to the CPU with just the right instructions at the right addresses, and you have a simple working program. And to answer your next question, yes. It was painful (we did this in high school). But I have to say that wiring up every chip in an 8-bit computer and writing a program manually gave me a depth of understanding of computer architecture which I could probably not have achieved any other way.
More advanced chips (like x86) are far more difficult to hand-code, because they often have variable-length instructions. VLIW/EPIC processors like the Itanium are close to impossible to hand-code efficiently because they deal in packets of instructions which are optimized and assembled by advanced compilers. For new architectures, programs are almost always written and assembled on another computer first, then loaded into the new architecture. In fact, for firms like Intel who actually build CPUs, they can run actual programs on architectures which don't exist yet by running them on simulators. But I digress...
As for compilers, at their very simplest, they can be little more than "cut and paste" programs. You could write a very simple, non-optimizing, "high level language" that just clusters together simple assembly language instructions without a whole lot of effort.
If you want a history of compilers and programming languages, I suggest you GOTO a history of FORTRAN.