Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space
The following approach is often referred to as reservoir sampling. Start scanning the set $S$ and maintain an index $j$ to the set. The first element you encounter satisfying the predicate, set $j$ to it with probability $1/1$. Update your choice for $j$ when you encounter the second such element with probability $1/2$. When you encounter the $k$th element satisfying the predicate, set $j$ to it with probability $1/k$.

The algorithm works in $\Theta(n)$ time and in constant space. For correctness, it should be shown that every item has an equal probability of being chosen and that the events they are sampled are independent. The second claim of independency is obvious: our decisions are not based on whether we have previously sampled items. The first claim (equal likelihood) can be proven quite easily with induction.

For details, see J. S. Vitter, Random Sampling With a Reservoir, algorithm R. For a more compact presentation, see for example these slides.