This isn't quite time travel, and it's not quite too expensive, and so on. Well, it's a nice idea, for sure, and it needn't be Java-specific either -- it generalizes.
Of course, you might need enormous amounts of memory or storage if you want to observe a busy process for a long time, but presumably one would only do use this tool for brief periods.
Also, BugJail is designed so that in normal use (webapps etc) it writes fast enough to database and never runs out of memory. Though, hardcode programs like databases and compilers exceed that, and currently don't buffer to disk, but crash it hard..
If you configure BugJail to capture only your own code/packages (--primary option) the disk usage is not that bad either. If you don't, you'll burn in the magnitude of ~10MB per second.
Give it a try, and let me know how it goes?