If I use a regularization (e.g. L2) can I not apply early stopping? I've seen that early stopping is a form of regularization that limits the movement of the parameters $\theta$ in a similar way that L2 Regularization penalizes the movement of $\theta$ to be closer to the origin.
Does that mean that I can avoid overfitting if I use a regularization other than Early Stopping and train for more than the epochs that it takes to overfit the model as prohibited by Early Stopping?
 A: Why not? You can use several methods of regularization at the same time, for example Elastic net combines $\ell_1$ and $\ell_2$ regularization. Different regularization methods work differently, so combining them sometimes can be lead to better results than using any one of them alone (like with Elastic net).
Notice that those regularizations work differently. With $\ell_2$ you essentially assume a Gaussian prior for the parameters that push them towards small values. Another example of regularization is dropout which forces the model to "do the same without those parameters". With early stopping, we train the model as usual but stop the training when we see a drop in validation set performance. With the two previous examples of regularization, you explicitly chose how you want to influence the model (make weights smaller, force building smaller "submodels") while with early stopping, your model "doesn't know" that you want to regularize it anyhow. It is perfectly fine to combine them because they do completely different things. We call them all regularization, but they are far from doing the same thing.
Additionally, early stopping makes the training faster since you potentially skip some iterations, which could be an added benefit in a scenario where your model trains for a long time. In some cases, this alone would be a reason to use early stopping nonetheless if you use other regularization.
A: It would be rather typical to combine a L2 penalty (or the closely related weight decay, plus possibly other regularization techniques such as drop-out) with early stopping when training neural networks or gradient boosted decision trees (e.g. LightGBM, XGBoost etc.). Esp. when training models that have the potential to massively overfit (like the ones I mentioned) and are more costly to train than some generalized linear model, this is very commonly done. Different regularization techniques have different effects and models may benefit from several of them.
E.g. early stopping is commonly used when you cannot figure out (or don't have the time to) how to set all the other regularization parameters in a way so that you can train to convergence without overfitting. Other regularization parameters like L1 and L2 penalties (as well as dropout in neural networks, which has been suggested to have a slab-and-spike prior like effect, sub-sampling predictors for trees or parts of trees is kind of similar to that, while sampling observations in tree based models or data augmentation for neural networks has more of an effect of emphasizing patterns that are seen in most of the data etc.) tend to reduce overfitting and will, as you suggested, let you train for more epochs/iterations before early stopping would be needed.
A: A @Tim suggests (+1), yes, you can use more than one form of regularisation at once, but the question would be why you would use early stopping in conjunction with L2 (or other) regularisation.  Early stopping is not all that easy to implement reliably, it is not always clear where the best error on the validation set is located, especially as the validation set is often rather small, and hence it's estimate of the loss may have high variance.  If you use e.g. Bayesian methods, or virtual-leave-one-out cross-validation for tuning the hyper-parameters, then you can use all of the data for fitting the model, rather than reserving some for the validation set, which is also likely to give a better model.
The advantage of L2 regularisation is that over-fitting is largely controlled by just optimising a single (usually) continuous hyper-parameter and we can train the model to convergence without worrying about overfitting.  Early stopping is also not as reproducible as regularisation as the number of iterations before stopping is more dependent on the random initialisation of the weights.
Note that if we initialise the weights to small random values, then early stopping is also encouraging the final values to be close to the origin, so it is likely to have a vaguely similar effect to L2 regularisation anyway.
