Why does this have to a sort of CAPTCHA? It could just be the payment method for your API. I'm not sure that the current difficulty of Bitcoin mining makes this practical, but the idea would be that in order to get to my precious API you mine a little bit for me.

This way you don't need to buy API credits or stuff like that, login and billing are somewhat conflated.

Maybe someone with better knowledge of Bitcoin can comment on the feasibility.