We address the problem of prioritized video streaming over lossy overlay networks. We propose to exploit network path diversity via a novel Randomized Network Coding (RNC) approach that provides unequal error protection (UEP) to the packets conveying the video content. We design a distributed receiver-driven streaming solution, where a client requests packets from the different priority classes from its neighbours in the overlay. Based on received requests, a node in turn forwards combinations of packets from the different classes to the requesting peers. Selecting a network coding strategy at every node can be cast as an optimization problem that determines the best rate allocation among the different packet classes so that the average distortion at the requesting peer is minimized. As the optimization problem has log-concavity properties, it can be solved by an iterative algorithm, with low complexity. Our simulation results demonstrate that the proposed scheme respects the relative priorities of the different packet classes and achieves a graceful quality adaptation to network resource constraints. Therefore, our scheme substantially outperforms reference schemes such as baseline network coding techniques as well as solutions that employ rateless codes with built-in UEP properties. The performance evaluation additionally provides evidence about the substantial robustness of the proposed scheme in a variety of transmission scenarios.