Random algorithm termination
The question "Does it terminate?" isn't well-formed.  You need to define more precisely what you mean by that question before it can be answered.


Is it guaranteed to terminate on all possible execution traces?  No.  There exists an execution trace where it never terminates.
Does it terminate with probability one?  Yes.  If you flip a coin until you first get heads, the probability of getting a never-ending sequences of tails is zero.
Is the expected number of repetitions until termination finite?  Yes.  If you flip a coin until you first get heads, the expected number of flips is finite (it is the expected value of a geometric distribution).


So, the answer to the question depends upon precisely which of those questions you meant to ask.  Normally, that's about all we can say.

Usually, if it matters, we try to define what we mean by "terminate" more precisely.  For instance, in the definition of the Halting Problem, "terminates" is specified to mean "guaranteed to terminate on all possible inputs and all possible execution traces", and the formalization of the Halting Problem implicitly restricts us to deterministic algorithms (more precisely, to Turing machines, which are necessarily deterministic; they don't have access to randomness).  Anyway, in general, if the differences matter, it's your job to specify exactly which meaning you have in mind.