But the blocks themselves are found just by (effectively) brute-forcing SHA2.
Not quite, but very close. A block is found when the resulting SHA2 hash is below a certain value dictated by the current difficutly.
But the blocks themselves are found just by (effectively) brute-forcing SHA2. What prevents someone from doing that to an arbitrary old block to (say) remove a transaction and thus double spend?
Instead of just being less than the value the difficulty, to replace a block, the value has to be exactly identical to the existing block hash. This is equivalent to finding a block with the absolute highest difficulty that bitcoin could possibly ever have.
The odds of your producing a block with different content and the same hash is 1 in 2^256. There isn't sufficient energy left in our star to accomplish that even given a planetary sized super computer operating at the thermodynamic limit for the next four billion years.
That sounds about right.
What prevents this is the subsequent blocks.
If you mine a replacement block for block #199999, you change its hash. Because that hash is stored in block #200000, you'll change the content of that block and have to remine it. Then you'll have to do the next block and so on, all the way to the end of the chain. As of this writing, that's another 31375 blocks. Nontrivial no matter how much brute force you throw at it!
Solving a block doesn't mean brute forcing for a specific hash. It means brute forcing for a hash in a particular range; many valid hashes would be possible, so it's a much easier problem than looking for a specific hash. So you can't simply try to solve a modified block #199999 for the same hash as the real #199999; that would be a much more difficult problem.
To replace a block
without having to recompute the entire chain afterwords, you would have to find a hash collision with the existing block. Brute forcing this hash is basically impossible.
