Looks like the Gallery block itself employs a filter to, if necessary, manipulate its inner Image blocks. Wonder if a similar filter could be used to simply shuffle $parsed_block['innerBlocks']? https://github.com/WordPress/WordPress/blob/dd87b5a4bd237d347f9b5bd2e493200b3945ff79/wp-includes/blocks/gallery.php#L19
That is, until https://github.com/WordPress/gutenberg/issues/9701 is fixed.
Could be wrong, though.