We have this issue in the fish shell. There's a single shared history file, and multiple shell instances may append to it at once. We use fcntl() locking but we do in fact have users who have $HOME on nolock NFS, where locking fails.

Our strategy is to keep the history as append-only, with periodic "vacuums" that rewrite the file into a temporary and move it into place. Even the appends in principle could be split, as NFS provides no guarantees here, but in practice writing individual items seems to be atomic when done with O_APPEND.