This particular construction would remain the same regardless of the person or people being spoken to. I think this has something to do with the fact that there is technically no grammatical subject here because the person being spoken to is in the dative case. Sorry I don't really know the grammar behind this.
It's an adverb, not an adjective - adverbs don't change in Russian. The confusing part is that it's an adverb referring to the omitted verb - есть. However, in all constructions of the type "мне/тебе/вам/им/ей/ему XXXo", "XXXo" is an adverb (стыдно, плохо, хорошо, холодно, жарко etc).
Why do you you think we are talking about the past?
"Вам должно быть стыдно"="You have to be ashamed" (now).
"Вам должно было быть стыдно"="You had to be ashamed" (in the past).
In any case, pay attention to how you would say it in the past tense in Russian: you cannot just replace быть→было since "быть стыдно"="to be ashamed" and so that быть must remain there.
I always forget when to keep "быть"
Since "быть" is the infinitive form, not the present tense, changing it to the past tense would be very illogical. You always keep it, just like you would keep "to be" in English. And if there is no explicit present tense verb, which you could readily change in a construction like this one, you just add "было" for the past tense or "будет" for the future tense.
As I understand it, to say вам стыдно is literally "to you [there is] shame", so if we want to say "you have to be ashamed", we have to keep the dative construct because that's how стыдно works, so the new literal sentence has to be "to you [there] must be shame", in Russian вам должно быть стыдно. Должно is an adverb modifying быть стыдно, while with я должен it's a predicate adjective modifying я.