Is there an algorithm for random sampling from a priority queue with probability proportional to priority?
This is exactly what the A-Res algorithm is for
If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time.  The way you achieve this is:

For each sample: randomly generate a number between from 0 to 1
Raise the result to the power of (1/weight).

It can be shown that a sample with N times the weight of another sample is N times more likely to be greater (have higher priority)