First-seen-safe replace-by-fee as detailed here https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-May/008248.html  by Peter Todd  seems to be a very suitable option and route which balances FullRBF while retaining  the significant 0-conf use case.

This would seem like a good way forward.