Someone knowledgeable please tell me there is a solution to this.
First off, let me give you the name we call this attack. We call this attack the "Finney Attack". Feel free to Google it for more discussion of it.
How could retail trust bitcoin if miners could sometimes steal from them?
Well, let's start out with the simple answer: they just have to. However, that's not as big of a deal as you think, since most retail already accept a form of payment that can be reversed by a determined attacker
100% of the time: credit cards. Therefore, 0-confirmation transactions are, in many ways, actually safer than one of the most common ways people already transact.
As far as preventing it, once we are in a world with no block subsidy, merchants can chain the fees for currently unconfirmed transactions in such a way that the longer it takes the attacker to find a block, the more fees they would be forced to give up because the fees were dependent on the transaction that was double-spent.
Credit card reversals aren't such a big problem. They affect your trust and you can only reverse so much until you lose your card and the ability to reverse. A reversable transaction that is not tied to trust is completely different issue.