I've got to get this idea written down so that I can go back to doing other things... it is too distracting as-is.
In a nutshell -- more or less Devel::Trace except that at each step you record all of the lexical (global?) state. Then you can not only see the full execution history of your program, but the value of every variable at every point.
Now of course from the idea comes all of these questions -- do we store all that or just some of it (just what changes). Do we only keep local lexical scope at each step since the rest can be reconstructed? How do we record this... do we summarize it somehow? And so on.
But ignoring all that... the next idea that comes to my mind is to toss this into CGI::Inspect as a module, so that you can use the GUI browse not just the current lexical state (there is already a plugin for that), but also the complete historical state as well.
I got the idea from the Omniscient Debugger, but I'd actually seen it before in its more highly evolved form in the OCaml Debugger. The OCaml Debugger doesn't have to actually save all that state though, since in a lovely functional language you can actually just reconstruct the previous state (I believe). Still.
(If you're still reading and want something even MORE insane, then your homework is to use Nothingmuch's delimited continuations in perl and make it so that you can actually resume any of the historical states).
Code might eventually show up at http://thelackthereof.org/projects/perl/Devel-TraceState or perhaps Devel-TraceState.