@michaelten have you seen Circles? It's a cryptocurrency for universal basic income that's designed to address the verification issue. I just discovered it today—I have no involvement with it. Their approach to the verification problem is to:

1. Use a network of trust to establish value (for example: if you trust my coins because you know me, they have value).
2. Use "validators" to help people establish trust, especially if they don't know anyone currently using Circles.

The file linked above provides many details, and examples, and is worth a read. I may also summarize it and try to connect with the people who launched it.