Will the same TNT pattern always give exactly the same blast pattern if ignited in the same way? Is there any element of TNT or other explosive's detonation that is random?
No, explosions do have random elements, and are therefore not deterministic.
The Minecraft Wiki has an in-depth analysis of how explosions work in Minecraft. The relevant bit:
So an explosion consists of lots and lots of separate "blast rays" that have a random variance of up to 30%, and are therefore non-deterministic.
The article even answers your question outright: