We investigate the effect of new stellar models, which take rotation into account, computed for very low metallicities on the chemical evolution of the earliest phases of the Milky Way. We check the impact of these new stellar yields on a model for the halo of the Milky Way that can reproduce the observed halo metallicity distribution. In this way we try to better constrain the ISM enrichment timescale, which was not done in our previous work. The stellar models adopted in this work were computed under the assumption that the ratio of the initial rotation velocity to the critical velocity of stars is roughly constant with metallicity. This naturally leads to faster rotation at lower metallicity, as metal poor stars are more compact than metal rich ones. We find that the new Z = 10-8 stellar yields computed for large rotational velocities have a tremendous impact on the interstellar medium nitrogen enrichment for log(O/H)+12 < 7 (or [Fe/H]< -3). We show that upon the inclusion of the new stellar calculations in a chemical evolution model for the galactic halo with infall and outflow, both high N/O and C/O ratios are obtained in the very-metal poor metallicity range in agreement with observations. Our results give further support to the idea that stars at very low metallicities could have initial rotational velocities of the order of 600-800kms-1. An important contribution to N from AGB stars is still needed in order to explain the observations at intermediate metallicities. One possibility is that AGB stars at very low metallicities also rotate fast. This could be tested in the future, once stellar evolution models for fast rotating AGB stars will be available.