At least for ARM on Linux, the kernel does provide cmpxchg in the VDSO, but I think that is for support on older ARM architectures. IIRC, the ARMv7 does not need to use the kernel helpers.
Yes, pre-ARMv6 does not have the load-link/store-conditional instructions.
The Linux kernel hack for that is actually kind of awesome. Notably, it's not a syscall and you don't enter the kernel to do them. Since pre-ARMv6 is always single core, it simply becomes a matter of detecting you are in the middle of an atomic op at interrupt time, and patching the result. This means the atomic op has to happen at a well-known (kernel-provided) address. Details here: http://lwn.net/Articles/314561/
I'm also aware of some older systems that needed kernel intervention for atomic ops. But on x86, ARMv6+, even no longer relevant arches like SPARC, POWER, ... this is not the case. It really is rare that the kernel needs to do this job these days.
Edit: ARMv6, not ARMv7, per the link I provided...
https://www.kernel.org/doc/Documentation/arm/kernel_user_hel...