This paper studies the electric vehicle (EV) charging scheduling problem to match the stochastic wind power. Besides considering the optimality of the expected charging cost, the proposed model innovatively incorporates the matching degree between wind power and EV charging load into the objective function. Fully taking into account the uncertainty and dynamics in wind energy supply and EV charging demand, this stochastic and multistage matching is formulated as a Markov decision process. In order to enhance the computational efficiency, the effort is made in two aspects. Firstly, the problem size is reduced by aggregating EVs according to their remaining parking time. The charging scheduling is carried out on the level of aggregators and the optimality of the original problem is proved to be preserved. Secondly, the simulation-based policy improvement method is developed to obtain an improved charging policy from the base policy. The validation of the proposed model, scalability, and computational efficiency of the proposed methods are systematically investigated via numerical experiments.