I have a question. If someone wanted to overwrite a portion of the Bitcoin blockchain with random data and have it still validate in place of a correct block, would this be computationally difficult/impossible?
Yes. The client have to validate every single thing in the block. Changing any component of the transaction will change the merkle root and in turn the block header. The block hash would be changed completely and as stated above, collisions aren't possible as of now. You can, of course choose to omit that transaction but that would omit the UTXO as well and it would be unspendable.
So the question is, "is it practically possible to overwrite those portions of a bitcoin block that currently contain URLs to apparent CP repositories and still have the block validate properly?"
I know to do this to substitute useful data would be practically impossible. But if one is looking to destroy existing data by overwriting it with any other random string that would compute the same hash (could be completely random in place of these URLs), does that then make the exercise within reach from a computational perspective?
Not possible. I doubt everyone would be with this, especially given that it would be considered a censorship (though it isn't morally correct to promote such content IMO).