You can disable interrupts when modifying locking primitives, and save/restore the CPU context when interrupts are entered/exited. You can also minimize the amount of changes that any interrupt handler can make within the interrupt context.
It's not really that bad, and plenty of microcontrollers lack atomic operations.