Is it possible to program in binary?

Of course. It's more commonly called machine code. It's basically assembly language without the mnemonic devices. Someone who knows assembly very well could program in machine code with additional effort, referring to opcode listings (e.g. x86) as needed.

Would I do it? No. Even assembly is only useful in rare circumstances, and there's no reason (beside demonstrating your skills) to reject the assembler's help.

Since you asked about hello world, you should check out this article. He shows how he wrote, then optimized, an x86 ELF program to output it. It was originally written in nasm then modified in a hex editor.

It's very much possible to memorize machine code equivalent of assembly instructions. Actually, when writing code in assembly language, one often happens to see hex code through machine code monitors, disassemblers, assembly listings, etc. As a result, over time some instructions can be memorized in their hex form without any extra effort.

• In the picture an 6502 ROM monitor is seen, where hex code and assembly mnemonics are shown side by side.

Second skill you're going to need is to transform hex code into binary which is quite easy with a trick I'll explain in a bit.

Think of the following instructions:

OPCODE       HEX
LDA #imm     0xA9 imm
STA adr      0x85 adr
STA (adr),Y  0x91 adr
LDY #imm     0xA0 imm

With above opcodes memorized only, we can write the following machine code using only pen and paper:

0xA9 0x00 
0x85 0x01 
0xA9 0x02
0x85 0x02
0xA0 0x00
0xA9 0x01 
0x91 0x01

Actually the above is the following assembly code in mnemonic form:

LDA #00
STA $01
LDA #02
STA $02
LDY #00
LDA #01
STA ($01), Y

• The above code puts a white pixel at the top-left corner of screen in 6502asm.com assembler/emulator, go ahead and try it out!

Now the trick for converting hexadecimals into binary and vice versa is to work it out only for nibbles (4-bit values).

First, remember how to convert binary into decimal. Every time you see 1, multiply that by its binary power. E.g. 101 would be 4 + 0 + 1 = 5. It can be visualized like this:

1   1   1   1 --> binary points
|   |   |   |               
v   v   v   v               
8 + 4 + 2 + 1
|   |   |   +---> 2^0 * 1   Ex: 13 is 8 + 4 + 0 + 1
|   |   +-------> 2^1 * 1             1   1   0   1 -> 1101 (0xD)
|   +-----------> 2^2 * 1   Ex:  7 is 0 + 4 + 2 + 1
+---------------> 2^3 * 1             0   1   1   1 -> 0111 (0x7)

With this in mind, and well practiced, the following should be possible:

LDA #00     -> 0xA9 0x00 -> 1010 1001 0000 0000
STA $01     -> 0x85 0x01 -> 1000 0101 0000 0001
LDA #02     -> 0xA9 0x02 -> 1010 1001 0000 0010
STA $02     -> 0x85 0x02 -> 1000 0101 0000 0010
LDY #00     -> 0xA0 0x00 -> 1010 0000 0000 0000
LDA #01     -> 0xA9 0x01 -> 1010 1001 0000 0001
STA ($01),Y -> 0x91 0x01 -> 1001 0001 0000 0001

With some retro computing spirit, motivation and fun, we could actually have written the entire code in binary without writing down the intermediate steps.

On a related note, Paul Allen coded a boot loader for Altair 8800 with pen and paper on an airplane, and possibly had to translate it to binary also with pen and paper: https://www.youtube.com/watch?v=2wEyqJnhec8