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.
