It is possible with the help of flowcharts and pseudo-code; the issue I've run into many times is depending on the class, you'll lose student interest over not actually doing anything. If it is a matter of limited resources, ala no computers, then go for it, but looking back, I'd feel a little short-changed if I couldn't walk out of the class without a functional program, no matter how insignificant.

This is where I liked MIT's EdX course. Mostly Python interpreter, but around the end you were given a GUI simulation of controlling a Roomba. You wrote the Roomba's logic and then ran the simulation. You could walk away from the class and say 'Look at this... I built this'.