despens: I think this right is formulated too specialized. The real demand should be that all data is exposed to the user in an universal, manageable way, for example the file system (see http://userrights.contemporary-home-computing.org/xmvw3/ ), preferrably in cleartext format.
If the browser's history is saved in ~/.browser/history.txt there is no need to demand a function especially for the deletion of this data. In fact, many more things than deletion could be made, for example syncing, manipulation, etc.
This is not possible if software is putting everything into databases that require extra knowledge to handle.