What if notebooks re-executed all cells in order as you type? That would solve the ordering and hidden state problem. To speed that up you could take a snapshot of the program state at each cell and re-execute from the snapshot of the cell preceding the cell you're modifying.
The advantage of a notebook over a repl is that the code you typed stays there and can be re-run and modified later. Re-executing all cells in order ensures that that actually works.
You can do away with the cell concept, and instead have some way to annotate which lines display their output. Then the distinction between an editor and a notebook almost disappears. An editor plus a way to annotate which lines' outputs are displayed, plus a way to type rich text, becomes a notebook.
Even better, you could allow users to display the output of lines inside functions, and have a way to select which concrete call is actually displayed. Sean McDirmid has already implemented such an editor. This removes the incentive to avoid abstraction, because it allows you to display outputs even if you put code inside a function or class. It's even better than a repl in this regard, and it doubles as a powerful debugger that can navigate through the execution.
The navigation works similar to an IDE's go to definition, except that when you go to definition on a call, it sets the concrete execution context of the call. For instance,
function foo(x)
y = x+2
return 3*y
end
foo(5)
foo(6)
If you click on the foo(5) call then it jumps to the definition of foo and sets x=5 and displays the outputs of expressions you've annotated, such as y = x+2. A similar mechanism allows you to pick the iteration of a loop. It even works fine in the presence of lambdas, allowing you to debug through callbacks (unlike conventional debuggers).