Would you use a crypto-currency backed by destroyed Bitcoins? You would send some Bitcoins to a specific blackhole at a certain time and the blockchain would credit you with 1 DestroyCoin.
Once all Bitcoins are destroyed, there would be a total of 21 million DestroyCoins.
Miners would be paid through transaction fees alone.