The anticipated high electric vehicle (EV) penetration motivates many research efforts to alleviate the potential associated grid impact. However, few works discuss the crucial issue: quality of service (QoS) degradation caused by competing for charging resources. This issue arises due to the limitation on power supply and charging space that charging stations can usually provide. Our work studies this issue and proposes an operational scheme that optimizes QoS for EV users while satisfying the stability of the power grid. The scheme consists of two levels. The lower level deals with charging rate control, for which we propose an efficient algorithm with provable QoS-optimal allocation of power supply to EVs. The upper level handles charging demand balancing, for which we design two approximation algorithms that schedule EVs to multiple charging stations. One algorithm is a 3-approximation with polynomial complexity; while the other is a (2+ϵ)- approximation using a fully polynomial time approximation scheme. Through extensive simulations based on realistic data traces and simulations tools, we demonstrate the efficiency and efficacy of our operational scheme and further provide interesting findings from in-depth analysis of the experimental results.