On the "purely functional" end, any stochastic algorithm is by definition not pure in the "referentially transparent" sense, so that's right out, and building a PRNG into the data structure is probably suboptimal.
As far as persistence/immutability go, the skip list doesn't seem well suited to that, either--any time you change an element, you'd have to replace all the elements with pointers to it, and elements with pointers to those, and so on recursively. There are standard solutions to this, but all would entail nontrivial changes to the structure.
In the end, it would be easy to make something not obviously broken that looked like a skip list, but I don't know whether it would have the same performance characteristics, or even worthwhile performance at all.
Given that skip lists are, in essence, a way of retrofitting some of the benefits of a tree structure onto a linked list, I suspect it would be more worthwhile to find an existing immutable, functional tree structure and retrofit some of the benefits of a linked list onto it.