Yes! With the new version 7.0 gdb, you can do exactly that!
The command would be “reverse-step“, or “reverse-next“.
You can get gdb-7.0 from ftp.gnu.org:/pub/gnu/gdb
If you run into the error: Target child does not support this command. then try adding target record at the beginning of execution, after starting run.
Edit: Since GDB 7.6 target record is deprecated, use target record-full instead.