Distributing blocks with validation and non-dependant list generation
How about embedding each block's MAC to the next? So that $b'_0=b_0||MAC(b_1)$, with the last block having the MAC of $b_0$. To make it even easier to identify a corrupt block, $$b'_n=b_n||MAC(b_{n-1})||MAC(b_{n+1})$$

where $||$ denotes concatenation. To identify the order of the blocks, simply try to fit them together as they come, or embed each block's $n$ to it.