The Prisoners and the Chessboard

There's a long tradition in mathematics of puzzles in which someone asks some prisoners to perform some bizarre task. Usually, if they can't complete the task, they are to be executed. Here is one of my favourite examples of the genre (which I only heard for the first time relatively recently).

So, the evil guy who kidnaps people and sets them bizarre mathematical tasks which they have to complete or be executed has kidnapped you and your friend Bob. He sets you the following bizarre mathematical task:

I will take you into a room in which there is a chessboard. There is a coin on every one of the squares of this chessboard, showing either heads or tails. I will then tell you which one of the squares has the key to the door of the prison under it. After this, you will be allowed to turn over exactly one of the 64 coins and then be escorted from the room.

Immediately after this, Bob will be brought in, and will be asked to find the key. If he can locate it you're both free to use it to unlock the prison and leave. If not, you'll both be eaten by rabid wildebeest.

You and Bob are free to discuss a strategy before you are taken into the room with the chessboard - what should you do?