"Where is his shoe?"
Translation:Wo ist sein Schuh?
Well, sorta. Really, it's nominative here because sein Schuh is the subject. The W-Fragewort "wo" is not a replacement for the subject. So, although you're right about sein and werden (and I'd never really thought about bleiben that way, but I guess I can't think of a time where it would take a direct object), that's not really why sein Schuh is not accusative in this case.
It's nominative because it's the subject. Turn it around and think of it this way: Sein Schuh ist wo? Sein Schuh ist unter dem Tisch. Sein Schuh ist neben der Tür. Sein Schuh ist ganz verloren.
Or at least, that's my opinion. I see you've done an insane amount of work in many languages, so you may very well know better than I. :)