The uncoordinated charging of large electric vehicle (EV) fleets could have an adverse influence on power network operation. To guarantee the secure and economic operation of power grids, vehicle charging needs to be coordinated to minimize the power supply cost, while catering vehicle charging requests. Provisioning large-scale fleets scheduled at fine timescales, the task of EV scheduling is tackled here by properly adopting the Frank-Wolfe method. Upon devising an optimal step size rule, the novel scheme is shown to enjoy fast convergence rate, especially during the first iterations. The derived charging protocol features affordable computational requirements from vehicle controllers and minimal information exchange between vehicles and their aggregator. To cope with random cyber delays in the communication links between vehicles and the aggregator, an asynchronous version of the charging scheme is also studied. Interpreted as a block stochastic Frank Wolfe algorithm, the latter ensures feasibility across iterations, converges in the mean, and enjoys the same order of convergence rate attained by its synchronous counterpart. Numerical tests demonstrate the advantage of our deterministic scheme over a state-of-the-art projected gradient descent alternative, as well as the robustness of its stochastic counterpart to asynchronous updates.