Apart from the problem of recently slow block discovery times, on average the new blocks are only around 200K (containing around 200-300 tx's) despite a large queue of unconfirmed transactions.
As BTC is at record highs is it not possible for miners to be a little more generous and include more tx's (so the blocks are closer to the 1MB limit)?
Many are now waiting days for their first confirmation and it certainly doesn't look good for talking about scaling (if we want to keep saying zero or little fees - and I am not talking about dust or invalid transactions due to no fees when the spec requires them).
At least if there were some way to "add a fee" to an existing tx one could get it to process but instead now if you didn't set your client to include a mandatory fee you just wait, and wait, and wait.
I think your idea is an excellent one, CIYAM.
I learned yesterday while doing some "banking" that the blockchain.info app doesn't include fees when they are not strictly required (despite selecting the "generous fee" setting). I have a single >1 BTC unconfirmed transaction that is now almost 24h old (all my transactions with fees went through immediately). This would spook someone new to bitcoin if they thought something got screwed up and thought that now those coins may be lost.
So I think your idea is great, but it would also be good if all the wallet software out there was more proactive in ensuring the default settings will "get the job done."