Short summary: entice all transactions (from EOAs - non-contract accounts) to include a hash of a recent block to confirm its validity.

In short-term, block producers' incentives can be ensured by slashing (eg. removing incurred rewards or locked deposit) or other solutions. In the long-term they don't work because there's no locked deposit to penalize at the correct chain.
However, if every valid transaction had to include a hash of a recent block they could be counted as a voting stake. In the long run, total stake validating the correct chain would comprise a very high percentage of all coins - making the nothing at stake attack much harder.

Details:
1. At block B_1, assign every EOA voting power equivalent to its balance.
2. Sender account of a transaction that confirms block B_1 must exist at B_1. Which also means that the transaction can only be included in a descendant of B_1.
3. Transactions from accounts that confirm a future block B_n (n>1) that have B_1 as an ancestor, confirm B_1 implicitly according to their voting power (balance) at B_1. (which means it's usually going to be zero)
4. Votes from same accounts don't add up (ie. the maximum stake voting for a block is 100%).
5. Block generation is counted as a vote in the same manner.

What this means is that stake voting for old blocks is going to approach 100% of EOAs and staking accounts, as eventually even dormant accounts are likely to do at least one transaction.

Valid chain criteria:
For most recent blocks (current time - validators' deposit lock period) ignore transaction votes and proceed according to a separate network consensus algorithm. For older blocks, chain with most stake votes wins, ie:
For every child y of a known valid block X, y with the highest voting stake is assumed valid.

Contracts:
Transactions from contracts don't vote because there's no clear way to connect intent with their total balance.

edit: Example
Block B_1:
Account A1 has a balance of 100 ETH. Account X1 has a balance of 10 ETH.
Block B_2:
A1 transfers 50 ETH to A2 and 50 ETH to A3, explicitly confirming B_1. His counted voting stake is 100 ETH because he had 100 confirmed ETH in B_1.
Block B_3:
A2 transfers some eth to some other account. He can explicitly and implicitly confirm only B_2 with 50 ETH because his account doesn't exist before that.

Transaction votes are:
B_1 100 ETH (from A1's tx in B_2),
B_2 50 ETH (from A2's tx in B_3),
B_3 0.

Block B_4: A3 does some transaction, explicitly confirming block B_3.
Now transaction votes are:
B_1: 100 ETH (explicitly from A1's tx in B_2),
B_2: 100 ETH (explicitly 50 ETH from A2's tx in B_3 implicitly 50 ETH from A3's tx in B_4),
B_3 50 ETH (explicitly 50 ETH from A3's tx in B_4),
B_4 0

A1's account is empty since B_2 so he sells his private key to attacker, who starts to generate his own chain, forked before or at B_1. He can confirm his chain with 100 ETH, which means both forks are now equivalent. However, as soon as X1 does a transaction on the main chain, confirmation for block B_2 goes up to 110 ETH, while the fake chain only can confirm 100 ETH. The main chain wins thanks to X1's transaction.
This makes the nothing at stake attack infeasible.

Thoughts?