Short answer: yes, captchas are doomed, and I have no idea how to replace them.
Robots are tenacious little beasts, and are perfectly happy trying something over and over. This means that any little Turing test cannot be multiple choice, and must be available in large quantities.
Suppose you have a multiple-choice Turing test with ten possible answers. This means that, at worse, a bot has a 10% chance of solving it. This means the bot only has to hammer your servers ten times as much to get in. For your typical bot, this isn't a problem.
Suppose you have a limited number of captcha-replacements. These can be fairly easily programmed in, so that the bot knows that a JPEG with this checksum requires that answer.
Now, another requirement is that a captcha-replacement has to allow real humans to solve it. This means that it can't be too demanding. If you display a picture of, say, a Boeing 747 and ask what it is, you have to be prepared for answers like "airplane", "aircraft", "aeroplane", "airliner", "Boeing 747", "747", "passenger plane", "Airbus", and so forth, since different people will answer in different ways, and people aren't always perfect in their understanding.
It also means that any of these devices can be solved by other humans, either working for pennies in poor countries, or by solving echoed versions to get into porn sites (both techniques have been used).