Probabalistic Polynomial-time Algorithms & One-way functions
A probabilistic algorithm uses random numbers to define the next step it should do (google for instance "Monte Carlo Algorithm").
"Random coin tosses" merely says that the random numbers are equally distributed.
The algorithm A will use the random numbers only internally, it will not output any random number. 
But A's output will depend on those random numbers.
Therefore, it will output a correct pre-image only with a certain probability.