Simulations generally show that non-self-gravitating clouds have a lognormal column density ($Sigma$) probability distribution function (PDF), while self-gravitating clouds with active star formation develop a distinct power-law tail at high column density. Although the growth of the power law can be attributed to gravitational contraction leading to the formation of condensed cores, it is often debated if an observed lognormal shape is a direct consequence of supersonic turbulence alone, or even if it is really observed in molecular clouds. In this paper we run three-dimensional magnetohydrodynamic simulations including ambipolar diffusion with different initial conditions to see the effect of strong magnetic fields and nonlinear initial velocity perturbations on the evolution of the column density PDFs. Our simulations show that column density PDFs of clouds with supercritical mass-to-flux ratio, with either linear perturbations or nonlinear turbulence, quickly develop a power-law tail such that $dN/d log Sigma propto Sigma^{-alpha}$ with index $alpha simeq 2$. Interestingly, clouds with subcritical mass-to-flux ratio also proceed directly to a power-law PDF, but with a much steeper index $alpha simeq 4$. This is a result of gravitationally-driven ambipolar diffusion. However, for nonlinear perturbations with a turbulent spectrum ($v_{k}^{2} propto k^{-4}$), the column density PDFs of subcritical clouds do retain a lognormal shape for a major part of the cloud evolution, and only develop a distinct power-law tail with index $alpha simeq 2$ at greater column density when supercritical pockets are formed.