sorry, a captcha cryptocurrency is not possible unless you figure this out
This is not possible if the coin is open source (reverse engineering will be easy), but it's possible with a closed source code. But if it's closed nobody will use it.
Not even possible with closed source. Everything is open source if you know how to use a disassembler and a debugger.
There are a couple of opensource or free captcha implementations. You can embed it into the client or you can use it on the "pool" servers. The only issue with the second solution is the relative centralized nature as you need the captcha servers to keep the coin working. Writing a distributed solution where everything included in the client would be a lot of work but it could work well.
You are missing the point. How would you generate the capthas? The clients or the pool owners need to know the answer in order to generate the captchas. So they could cheat, and tell the answer to a friend and earn $ for nothing.
The problem is not the bots (at least not only the bots). Imagine there was a perfect captcha, with images, sounds, or whatever, that only humans could solve. Who would generate the challenges and then verify the responses?