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.
Looked at the wiki for Amazon Mechanical Turk and am fascinated by it enough to look into it more later.
I am not a dev nor anything else but just an observer who thinks it is obvious that human mining is the next big step.
Also my resources are near zero in every category so although I support the concept fully someone with abilities and resources will have to do it. I think it is good to discuss this kind of thing publicly since maybe someone else will read and get a useful idea but I mention it here because bitfreak or some other dev might do something with it. If you and bitfreak discussed the issue some good might result.
Although I am not a dev or coin person etc I do know enough of other things to respect the potential of 'human mining' and also to understand in some way the long term impact of that step once it is taken. It certainly goes past bitcoin.