Sublinear finite-precision sampling in a stream
The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number. 

Building block: sampling without arbitrary precision arithmetic

Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$).  Then one approach is to sample $y$ uniformly at random from $[0,1]$, find $x$ such that $F(x-1) &lt; y \le F(x)$, and output $x$.  This requires arbitrary precision arithmetic.

Here is a variant that avoids the need for arbitrary precision arithmetic, at the cost of making the algorithm a Las Vegas algorithm (so the worst-case running time is unbounded but the expected running time is nicely bounded).  Basically, we sample the bits of $y$ one at a time, and stop as soon as we know what answer the prior method would output.  At the $b$th stage, we know the first $b$ bits of $y$, i.e., we know $\tilde{y}$ such that $y \in [y, y + 1/2^b)$ and $2^b \tilde{y}$ is an integer.  Now, we find $x$ such that $F(x-1) &lt; \tilde{y} \le F(x)$.  If $F(x-1) &lt; \tilde{y}$ and $\tilde{y} + 1/2^b \le F(x)$, then we output $x$ and stop.  (In this case, we don't know what the exactly value of $y$ is, but we still know it satisfies $F(x-1)&lt; y \le F(x)$, so $x$ is certainly the right answer.)  Otherwise, we output nothing and continue, sampling the next bit of $y$.

What's the running time of this procedure?  The expected time until termination is $O(\lg n)$, where $n$ is the number of different possible values of $X$.  (Why?  Because at the $b$th stage, at most $n$ out of the $2^b$ possible values for $\tilde{y}$ will cause us to continue on to the $b+1$th stage.  In particular, once $b$ exceeds $\lg n$, each stage has at least a one-half probability of terminating.)  So, this gives a Las Vegas algorithm to sample from $X$, with exactly the right distribution, and with $O(\lg n)$ expected bits sampled from the RNG.

Solving your problem

Now we can solve your particular problem.  We simply apply Vitter's algorithm (e.g., Algorithm Y), but instead of sampling the random value $\mathscr{S}$ using arbitrary-precision arithmetic, instead use the method described above.

How many random bits do we need?  Based on the results in that paper, the expected number of times we need to sample $\mathscr{S}$ is $O(\log n)$, where $n$ is the length of the stream.  Also each time we sample $\mathscr{S}$ the expected number of bits we need to sample is $O(\log n)$.  Therefore, we'll need $O((\log n)^2)$ bits from the RNG, on average.

Also the total (expected) running time will be $O(n)$, if you use Vitter's efficient algorithms for sampling $\mathscr{S}$ (e.g., Algorithm Y and binary search or Newton's method).