Media distribution through application-layer overlay networks has received considerable attention recently, owing to its flexibility and readily deployable nature. On-demand streaming with asynchronous requests, and in general, with VCR-like interactions, nevertheless remains a challenging task. In this paper, we introduce the Skip List, a novel randomized and distributed structure that inherently accommodates dynamic and asynchronous clients. We demonstrate a practical skip list based streaming overlay with typical VCR operations. Our simulation results show that the skip list based overlay is highly scalable, with smooth playback for diverse interactivities, and low overheads.