I remember how I was surprised to find that you can implement compare-and-swap purely in software (with some caveats :) but still, IMO, preserving the idea). See, e.g. Peterson's algorithm. It does have a lock, but only for finite (and brief, if you will) moment, and, wrapped as procedure, is externally lock-free.

You still rely on ability to locally order operations in time (i.e., you have to be sure that you - the CPU - reads from that memory cell strictly after it completed writing into this one) - so there are restrictions for modern CPUs. You might have issues if you want to synchronize many threads/processes - as the locking delay may become too long. But still.