The challenge is to develop the coin in a way that stays ahead of automators and to anticipate the effect the coin might eventually have on local economies, i.e., anticipate problems that might arise.
I think you'd have to do something like Amazon Mechanical Turk where people submit tasks and have to pay for them, and then the system allows, but does not require, humans rather than bots to preform the tasks. People won't pay human-labor prices for tasks that can be automated, they will simply automate them, so such a market naturally attracts tasks that can't be automated.
Turning that into a mining algorithm is another matter. I can sort of think of ways that could work, but I'd have to take some time to work through the details, and I don't have time for it right now. Feel free to PM me to exchange ideas if you are working on this seriously.