Some browser APIs (such as playing video) are locked behind a user interaction. Do the same for the history API: make it so you can't add any items to history until the user clicks a link, and then you can only add one.

That's not perfect, and it could still be abused, but it might prevent the most common abuses.

EDIT: apparently Chrome tried that and it wasn't sufficient: https://news.ycombinator.com/item?id=47761349