When I was in high school, the introductory programming class didn't let us use a computer for about a month. Instead, we would get programs on paper, and would be asked to trace out what they did.

When I taught friends how to code, I was less strict, but writing out the steps on paper was still a big part of it. I also wouldn't let people make changes to their code without first telling me what they thought was broken, and predicting/explaining what the change would do.

I think it's a very effective approach.