Yes you can. An executable (using ELFs as an example, most formats are similar) is nothing more than some headers and bytes. The executable code can be modified in any way you please, as long as you're writing valid opcodes (the program will crash if it hits a bad opcode).

That said, it's usually much more complicated to change the size of the executable section (this requires modifying the headers and this tends to be a rather involved process), so usually if people are doing binary patches they are only modifying bytes, not adding or removing them.