I'm interested in this for the first use case. As for second case, as Ryan said, this is basically what we used to do. I think as far as deletes and such are concerned, we need to nail down what we do/don't want to do during a flush and during minor compactions.
HBASE-2248 we now have MemStore taking care of the ordering of duplicate versions, so within each StoreFile, they will be ordered with the most recent at the top. The only thing that remains to properly handle ordering of duplicate versions is cross-StoreFile.
One solution is to include sequence numbers for every KV in the StoreFiles. The other is this jira. I am +1 on this jira and have a general idea how to do it.