A novel, fully decentralized strategy to coordinate charge operation of electric vehicles is proposed in this paper. Based on stochastic switching control of on-board chargers, this strategy ensures high-efficiency charging, reduces load variations to the grid during charging periods, achieves charge completion with high probability, and accomplishes approximate “valley-filling”. Further improvements on the core strategy, including individualized power management, adaptive strategies, and battery support systems, are introduced to further reduce power fluctuation variances and to guarantee charge completion. Stochastic analysis is performed to establish the main properties of the strategies and to quantitatively show the performance improvements. Compared with the existing decentralized charging strategies, the strategies proposed in this paper can be implemented without any information exchange between grid operators and electric vehicles (EVs), resulting in a communications cost reduction. Additionally, it is shown that by using stochastic charging rules, a grid-supporting battery system with a very small energy capacity can achieve substantial reduction of EV load fluctuations with high confidence. An extensive set of simulations and case studies with real-world data are used to demonstrate the benefits of the proposed strategies.