For example ask him to upload his video with his ID. This video will be verified by another human operator.

In the end, user will be given some kind of identifier. He should present that identifier to anyone asking if he's a robot.

Of course that kind of verification will be paid. So you're paying $100 to get a verified identifier and then you keep that identifier (probably in the form of private key with signed public key).

There will be multiple certificate authorities who will issue those certificates to people. Rest of software companies will trust those authorities.

You need to renew that certificate every year.

If someone spotted your certificate being used in a nefarious schemes, your certificate will be revoked and you'll need to pay $5000 fine next time you'll ask for new certificate.

If you don't possess certificate, you're not qualified to be a human.