In this paper, we study the stochastic optimization of cloud radio access networks (C-RANs) by joint remote radio head (RRH) activation and beamforming in the downlink. Unlike most previous works that only consider a static optimization framework with full traffic buffers, we formulate a dynamic optimization problem by explicitly considering the effects of random traffic arrivals and time-varying channel fading. The stochastic formulation can quantify the tradeoff between power consumption and queuing delay. Leveraging on the Lyapunov optimization technique, the stochastic optimization problem can be transformed into a per-slot penalized weighted sum rate maximization problem, which is shown to be non-deterministic polynomial-time hard. Based on the equivalence between the penalized weighted sum rate maximization problem and the penalized weighted minimum mean square error (WMMSE) problem, the group sparse beamforming optimization based WMMSE algorithm and the relaxed integer programming based WMMSE algorithm are proposed to efficiently obtain the joint RRH activation and beamforming policy. Both algorithms can converge to a stationary solution with low-complexity and can be implemented in a parallel manner, thus they are highly scalable to large-scale C-RANs. In addition, these two proposed algorithms provide a flexible and efficient means to adjust the power-delay tradeoff on demand.