Managing the Quality-of-Experience (QoE) of video streaming for wireless clients is becoming increasingly important due to the rapid growth of video traffic on wireless networks. The inherent variability of the wireless channel as well as the Variable Bit Rate (VBR) of the compressed video streams make QoE management a challenging problem. In this paper, we investigate scheduling algorithms to transmit multiple video streams from a base station to mobile clients. We present an epoch-by-epoch framework to fairly allocate wireless transmission slots to streaming videos. In each epoch, our scheme reduces the vulnerability to stalling by allocating slots to videos in a way that maximizes the minimum "playout lead" across all videos. We show that the problem of allocating slots fairly is NP-complete even for a constant number of videos. We then present a fast lead-aware greedy scheduling algorithm. Our greedy algorithm is optimal when the channel quality of a user remains unchanged within an epoch. Our experimental results, based on public MPEG-4 video traces and wireless channel traces that we collected from a WiMAX test-bed, show that the lead-aware greedy approach results in a fair distribution of stalls across the clients when compared to other algorithms, while still maintaining similar or fewer average number of stalls per client.