Update
I now have a whole fancy library for random sampling in Clojure, including reservoir sampling with lots of extras (with and without replacement, weighting, seeds). It's available here:https://github.com/bigmlcom/sampling
A little snippet of Clojure for reservoir sampling: