shaver_rss2 pointed out this message. Apparently Michael Chastain wrote the very program I'm looking for, back in 1995. Nobody cared, the kernel APIs kept changing underneath it, and it died on the vine.

[...] The replayer is the cool part. It takes control whenever the target process executes a system call, annuls the original system call, and overwrites the target process registers and address space with the values that I want to be in there.

[...] If I put memory-access rule checking in at replay time, I can do better than e-fence, on stock binaries with no recompilation. Hell, I can do better than Purify on stock binaries and without tangling with their object-code-insertion patents.

I have enough information available in the proxy ptrace filter to implement PTRACE_SINGLESTEP_BACKWARDS. How would you like to have that capability in gdb? "Execute backwards until this data watchpoint changes." Imagine a graphical debugger with a scrollbar for time, where the top is "beginning of execution" and the bottom is "end of execution."

Yay progress.

Ok, the rest of the message reads as a "why does my genius go unappreciated" whine, but still, I want this program! The code is still available, but I'm sure not feeling motivated to try and port it to run on a modern kernel (it doesn't even support ELF binaries...)

It looks like after this message was sent to the linux-kernel list in 1999, there was a whole lot of talk, then three years of zilch. (I've mailed to ask if any progress was ever made. I'm doubtful.)

Update: He wrote back. No, nobody ever made it work on modern systems.