A solution: Discrete double auctions. Instead of continuous trading, the exchange can divide up the day into a series of small windows (say 100ms). When you come to trade in the market, you have to wait for the next window to open. You submit your order and you find out what happened at the end of the window. This way nobody has any timing advantage and the delay is barely noticeable to 'normal' traders (waiting 1/5 of a second is hardly an inconvenience). It also stops all the order-book shenanigans that HFT players get up to (where they stuff the book with orders and cancel/resubmit them at high frequency).
So why don't exchanges do this? They make a ton of money in fees, it simply isn't in their interest to prevent HFT at the moment. Change their incentives (ie. regulate differently) and they might actually do something about it.
Actually there are lots of discrete auctions in the electronic trading world. For instance the S&P futures contracts trade this way before the open and depending on your perspective they have more "shenanigans" being played by HFT players. Not less.
There are 2 major issues that no one brings up when they say "simply add discrete auctions". A) what happens when there are more participants on 1 side of a price than on the other, what is the tie breaker after price? B) How does this solve the distributed systems problem of multiple exchanges trading at the same time?
So why don't exchanges do this? They make a ton of money in fees, it simply isn't in their interest to prevent HFT at the moment. Change their incentives (ie. regulate differently) and they might actually do something about it.