Both of the past-tense examples sound somewhat archaic, but that is to some extent because the use of shall in the present-tense sentences does also, imo. (The use of present-tense may in the second sentence sounds formal, but not archaic.)
Probably the last person I heard use might and should with these specific meanings was my grandmother, who learned English as a foreign language about 100 years ago (literally). If your questions is whether you should :-) use the words with these meanings, I would say no, as it will simply be confusing. To convey the past-tense sense of these, you might have to come up with workarounds:
When he was at school, he was not allowed to go to the bathroom ...
He thought that they would go to the restaurant.
Hmm, that second one is tricky, but it's the result of substituting the non-archaic will for shall in the present tense.
The extent to which we can still call these preterite-present, is that they have present-tense uses for the past tense form. For example, while we can use could as a straight-forward enough (if irregularly formed) past tense of can in a sentence like:
I could run that far when I was younger, but I can't any more.
We can also use could in the present tense.
I could run that far when I was younger, but I *could*n't any more.
Including in forms where we must use could, and can wouldn't serve:
I could really do with a coffee right now.
Remember, that can and could are forms of the same word. You said "I don't see how can, will, may and shall express a past action or state", and the answer is rather than the past tense of those words—could, would, might & should can apply to the present tense.
Now for the history bit!
In Old English there were two main forms of verb; strong and weak. They differed in terms of how they were inflected for person, tense, number and mood. Indeed, we still have the legacy of this in Modern English, so some people still use the terms for Modern English.
A weak verb would change tense by having a set ending added to it. This is the case with most Modern English verbs (walk → walked, watch → watched, auction → auctioned).
A strong verb would have a change in vowel to change tense and sometimes mood. This is still the case of some of the Modern English equivalents (ring → rang/rung, bite → bit/bitten, come → came, shake → shook/shaken).
Because there are relatively few strong verbs in Modern English, many people don't use the terms weak and strong about Modern English, but just regular and irregular, considering all the remaining strong verbs as special cases.
The two also differed in how number and person worked with each type. There was a third class that would act like the strong for the past tense and the weak in the present tense, in this regard.
The fourth class were the preterite-present verbs, where a form you would normally have with a strong past tense, was used in the present tense, and then the other inflections were done as if they were weak. So for this reason, they had some qualities of past-tense verbs when they were in the present. Hence the contradictory name preterite-present.
Old English had many more preterite-present verbs than Modern English. The only remnants in Modern English are the auxiliaries. This was not the case in Old English in both directions; by which I mean that not only where many other verbs preterite-present, but that the auxiliaries weren't auxiliaries in Old English (they also weren't defective, you could say sculan in Old English while the closest translation "to shall" or "to should" isn't correct Modern English.
Willan was neither defective, nor preterite-present, though the modern will/would is both. It was a strong verb.
Best Answer
Getting back to the original question (asked 3 years, 8 months ago by someone who's left the group since), the actual answer is that whether you should consider modal auxiliary verbs to be inflected for tense depends entirely on what your grammatical system's definition of "inflected for tense" is, and how your grammatical system uses tense inflection.
For instance, some grammars of English insist that every sentence have a main tensed clause. Since modal auxiliaries can occur in simple sentences, these would have to be assigned a tense (typically Present, by default) by that grammar. On the other hand, your grammar might simply except modals from that requirement, or it might not have that rule at all, using something else instead.
No modern grammar that I know of distinguishes the historical present and past forms of modals (may, can, shall, will vs might, could, should, would, must) in any useful way, so the various final -t's and -d's are merely etymological curiosities, like the a-'s in awake, atop, aloft, and asleep.
A semantic past-present difference shows up with can/could in the ability sense, and will/would in the deontic 'willing to' sense. Both past descriptions refer to repeated behavior:
But that's about it; there's no tense or meaning difference between He might do it and He may do it -- both are possible, and that's it. Should has a special meaning as a weak must, both deontic and epistemic:
and, in the US at least, shall is not used for the future like epistemic will, but rather is restricted to two very special and limited deontic question constructions:
First person singular question - an offer to do a favor for the addressee
First person plural question - an invitation to do something with the addressee
And, as you note, there is no historic present tense for must, as there is in German, where modal auxiliary verbs are not defective verbs like English modals, but real strong verbs, with all their principal parts, inflected regularly for everything.
So, if your grammar (and every linguist creates their own grammar of their own language) requires English modals to have tense, Voila! they do. If not, not. If you prefer, some may have tense and others may not. Questions like this are not matters of fact; they're arbitrary, so you might as well take whatever answer you like. It's your grammar, after all.