If a blockchain cannot be rewritten, what happens to those coins that have its users lose their keys?
The coins just sit there unused and unclaimed (barring a brute force attack).
Some estimates are that the creator of bitcoin, Satoshi Nakamoto, holds around 1 million bitcoins. It's an estimate because all of Satoshi Nakamoto's bitcoin addresses are unknown but it's reasonable to assume the genesis block's bitcoin address belongs to Satoshi Nakamoto:
That bitcoin address remains untouched. A few people who are worried that Satoshi Nakamoto could theoretically sell off all the owned bitcoins have suggested that the Bitcoin Core code should be altered to remove all of the suspected bitcoin addresses owned by Satoshi Nakamoto to prevent a sudden sell-off.
There are also stories of people who accidentally threw away computer drives containing cryptocurrency private keys or accidentally deleted them.
As Satoshi wrote on bitcointalk.org on June 21, 2010:
"Lost coins only make everyone else's coins worth slightly more. Think of it as a donation to everyone."