What shall we do? Or what should we do? Or both?

[ROBINDESBOIS]

Difference between the 2 questions?

[Rusty]

Hard call. Sometimes they can mean the same thing. Sometimes they don't.

What shall we do? =
What are we going to do?
We're in a mess. How will we get out of it?
What course should we take?

What should we do? =
What are our choices? / Which choice is better?
What are we going to do?
We're in a mess. Which course of action will help?
Which course should we take?