For C/C++, the reverse execution support in gdb may be good enough (http://sourceware.org/gdb/current/onlinedocs/gdb/Reverse-Exe...)
"The Chronicle framework provides complete register and memory-level recording of Linux processes and efficient queries over the recorded traces."
Wow, I was looking for something exactly like this a while ago, but was unable to find it. I notice that these days with Google it's really hard to find a tool or project when you're looking for it especially if it's more obscure. Might be a consequence of the ranking rules that crowd lesser known pages out.
BTW I looked around a bit and found another similar system, based on QEMU instead of Valgrind, claiming to be faster, ie less runtime overhead while tracing, and also supporting kernel mode:
http://wiki.nss.cs.ubc.ca/Tralfamadore
Edit: never mind, the program does not seem to be publicly available, just papers
Worth checking out and it would be nice if someone could pick it up and develop it more actively.
http://code.google.com/p/chronomancer/