Here is a proposal for achieving consensus on transaction fees, based on the Slasher
[1] algorithm:
1. Fees would come from proof-of-stake blocks but would be voted for in each proof-of-work block.
2. Miners voting for lower fees in their proof-of-work blocks would have a higher probability of mining a proof-of-stake block.
3. Mined proof-of-stake blocks would select the fees voted for in the proof-of-work blocks providing their signing privileges.
This would create two opposite incentives for miners when voting for fees:
1. Higher fees would increase their profit when mining a proof-of-stake block that included those fees.
2. Lower fees would increase their chances of mining a proof-of-stake block.
So transaction fees should remain within a reasonable interval.
[1] http://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/
EDIT: There is a flaw in this proposal: miners with no long-term commitment would have an incentive to vote on arbitrarily lower fees merely to increase their mining probability while still enjoying the current, higher fees.
