I worked with Chris on Eve, which was the project he started after he hit a wall with Light Table, that wall being the limitations of programming languages you outline here. Eve did have strict no side effects requirements, and did have the ability to log and rewind programs. The bulk of our work was in nailing down a good set of semantics, and also in figuring out a good way to present those semantics to users (syntax, UI, etc.).
After writing countless programs in this style, which is very different from conventional programming, I have to say the Mario example is a nice demo, but in reality we didn't find time-travel useful in scenarios like that. What was infinitely useful though, was being able to trace the provenance of different values in your program for debugging. Since we kept information around that the compiler usually throws away, we could tell you exactly how a value or UI element was calculated, and give you tools for interacting with that history that just aren't possible in other languages. For instance, you could encounter a bug, pack up the state of your session, send that over to another dev, and he/she would see exactly the environment in which your code was executing.
You bring up the good point that not everything is written in this way, and so interacting with external code can be tricky. For example, you might have some code that sends out an email every time the system memory reaches a threshold. Now, you might get an e-mail you didn't expect, but you could go back and see exactly why that email was sent, and deduce the bug through the provenance tree.
As I said earlier, after writing programs in this style for 3 years, I'm utterly convinced we won't be programming in the future the way we program today. There were versions of Eve where we wrote very complex applications, from webapps to robotics, that didn't even feel like programming -- it felt more like forming a shape out of clay, where the clay in this case is a digital "material".
In the end, Eve couldn't get more funding because it wasn't a venture that was really set up to fit into the VC mold (and I'm still not sure how Chris and Rob convinced VCs to fund them in the first place), but I'm absolutely sure the current way of doing things will fade with time. It's going to take a lot more research and a lot more convincing, because there are a lot of people out there that for some reason don't want to see projects like this work, but as someone who went down the rabbit hole and gotten a glimpse of this future, I really just can't fathom how humans could be working with languages held back with so much baggage from the early days of computing in the year 2100 for example.
I'm curious though, why you suggest for a language to work like this you have to abandon Turing Completeness. This wasn't my experience at all, and we implemented a Turing Machine in Eve just to prove we were TC (http://incidentalcomplexity.com/2014/12/01/nov/).