At regular REL can players rewind the game state?
There is nothing in the CompRules about taking back legal actions, so when in doubt, ask the judge, unless you both want to risk a sanction in the worst case. He may nor may not allow it, and he may or may not require to be asked in the first place. In the end, a judge can give whatever ruling he wants, and the opposite of it on the next case. So there is no general answer.

That being said, in high REL, where a lot is on the line in the tournament, you probably won't see many of the situations as described by you, either because there are no inexperienced players, or nobody would agree to have a mistake taken back to get any advantage possible. In lower REL, like pre-Release or somesuch, if I were a judge I would definitely allow it to commend the sportsmanship and teaching effort of the more experienced player.