How to go to the previous line in GDB?

Yes, it is possible, and straightforward, now, with real hardware (ie. not just with a VM). GDB-7.0 supports reverse debugging with commands like reverse-step and reverse-continue, on native linux x86 machines.

There is a tutorial here: http://www.sourceware.org/gdb/wiki/ProcessRecord/Tutorial

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.