Nonuniform sampling band-limited gaussian white noise
As you mention, you could upsample the signal to a sufficiently high rate.

An alternative would be to compute an interpolation kernel for every desired output sample.  This would probably be pretty inefficient for a large number of output samples.  You could tabulate many interpolation kernels.  That would again leave you with a fixed set of possible offsets, but it might save you time and/or memory.