There is another solution. Reward people (other than miners) with micro-payments in return for running full nodes.