Requiring a percentage of old coins to be spent as fee will not work. People who are able to build a quantum computer can also spend a few more bucks to buy miners and mine the block containing the transaction themselves, without broadcasting it before.