TL;DR
It is both of what you found. To create water, you need hydrogen and oxygen in some form. The design of a fuel cell requires electrons to be moved and in exchange, some other charge has to move, here it is provided by the protons.
The lengthy explanation:
If we just combine oxygen and hydrogen and ignite it, it would (violently) react to water. It does this because it is an exothermic reaction. The interesting thing about a fuel cell is that we can control the flow of the energy that is set free during this reaction. We do not want to have just sudden heat. So at this point, a fuel cell is really just burning hydrogen with extra steps. But no matter how these steps look like, in the end you need both reaction partners. So yes, it is about "combine with oxygen for reduction".
Now to the "complete the circuit" part, and here it is important how the extra steps of burning hydrogen look like. In order to control the reaction, we now separate the gases with a membrane that can only be passed by hydrogen cations (protons). But molecular oxygen does not form a stable product with just protons, so we give the oxygen a few more electrons such that we have $O^{2-}$ and voilá, this is a nice reaction that can take place: $2 H^+ + O^{2-} \rightarrow H_2O$. Now we have to get the extra electrons for the oxygen from somewhere, and we have to put the spare electrons from the hydrogen somewhere, and again this is a perfect match. Since we blocked the direct way with the membrane, we use a wire to transfer the electrons from one place to another. We can plug in electrical load here which is driven by the energy that would normally be released by burning hydrogen (minus some losses). So you see, you need the proton to complete the circuit. No ions, no electric current. No electric current, no reaction.
About your other questions:
Yes you can use many different ions. This is what happens in batteries. A fuel cell is simply speaking a battery with certain specifications. Here is a list with many actually used combinations: Electric battery - Wikipedia
In any galvanic cell, you are creating an imbalance of charge due to the electrons pushed from one to another cell. This imbalance causes the reaction to stop at a certain point (very fast). The charge difference is then so large that it outweighs the reaction enthalpy and nothing happens anymore. To compensate, charges have to be moved from one part of the cell to another. A classic is to move sulfate ions via a salt bridge, because they don't participate in the reaction but can compensate the charge.