I know that an always block will be trigger on a change in any of the elements in its sensitivity list however, my question is what happens if a change in sensitivity list happens while the statements inside the always blocks are still being executed (due to a previous trigger). Does the always block begin execution again in a parallel thread or is triggering blocked until execution finishes first?
As soon as an always block is triggered, it will be executed from the beginning to the end. Verilog is a single-thread simulation engine, therefore only one block can be executed at a time. Nothing else could happen while an always block is executed, unless it contains delay statements or waits on events. In the latter case it will just yield to allow other blocks to being executed, then it continues.
If an always block changes its inputs by the end of the execution, then next simulation behavior depends on the type of the block:
With v2k/v95 always blocks you can end up with a zero-delay loop if you are not careful. In other words simulation can hang.
With SystemVerilog blocks you can get an interesting read-before-write condition (when a variable is read before it is written in the same block). This can potentially create simulation/synthesis mismatch.