What is meant by a theory to be (1) perturbatively renormalizable, (2) perturbatively non-renormalizable, (3) non-perturbatively renormalizable, and non-perturbatively non-renormalizable? In each case, what are at least one example of such theories?
Perturbatively renormalizable (or simply renormalizable) theories are those which can be consistently renormalized by tweaking values of a finite number of parameters to any order of perturbation theory. The key moment here is that the finite number of parameters is fixed prior to choosing the order of perturbation theory. We have to be able to make sense of the theory to any order by tweaking the same finite set of parameters. Examples of renormalizable $4d$ QFTs include $\varphi^4$ (parameters are the field strengths renormalization $Z$, the particle mass $m$ and the interaction coupling $\lambda$), Yukawa theory (both scalar and pseudoscalar), QED, Yang-Mills for compact gauge groups.
Perturbative nonrenormalizable (or simply nonrenormalizable) theories are those which aren't perturbatively renormalizable. Examples include $\varphi^6$ in $4d$, perturbative General Relativity.
I've never heard the term "non-perturbatively renormalizable", but I suppose what is meant is finite. Finite theories are those which admit a well-defined Quantum Mechanical definition with a Hilbert space (or a Gelfand triple), and physical observables as self-adjoint operators acting on it. An incredibly beautiful and nontrivial moment here is that finite theories can have perturbative expansions which are actually nonrenormalizable. The best example here is General Relativity in $3d$. It was rigorously quantized by Witten, but its perturbative series is a nonrenormalizable asymptotic expansion.
The ones which we can't formulate or define :) The logic is that quantum theories define effective actions, not the other way around. If we have a theory which can't be made sense of quantum-mechanically, then we don't have a theory at all.
All these distinctions are somewhat old fashion, in the modern understanding of QFTs as effective field theories, and whether a QFT is fundamentally renormalizable or not is a concern mostly for people who still believe in a QFT of everything. (Note that from a popularization point of view, this seems to be very important, but one should keep in mind that most people using QFT/RG are not really working on this issue of a theory of everything.)
(1) A perturbatively renormalizable theory is a QFT, where at each order of perturbation theory with a fixed UV cut-off $\Lambda$, one can redefine a finite number of parameters as a function of $\Lambda$, such that the limit $\Lambda\to\infty$ is now well defined. Note that this has to be done in that order : first, perturbation, then $\Lambda\to \infty$. The two limits do not necessarily commute. For instance, the $ \phi^4$ theory in 4D is perturbatively renormalizable, but does not exist in the continuum limit ($\Lambda\to\infty$ right from the start), that is, if one insists that the theory is defined directly with an infinite cut-off, with a finite interaction constant, then only the free theory is well defined.
(2) A perturbatively non-renormalizable theory is a QFT where this cannot be done. One needs to increase the number of parameters as one increases the order of the perturbation expansion. This does not mean that the theory is useless, only that one cannot get rid of the high-energy dependence with only a few parameters. This is the case of most theories.
(3) A non-perturbatively renormalizable theory is a QFT where the continuum limit can be taken, with only a few parameters needed to completely parametrize it. However, if one tries to expand in the coupling constant, and then take $\Lambda\to\infty$, then the theory seems to be non-renormalizable. This idea is behind the asymptotic safety scenario of quantum gravity, where one tries to perform non-perturbative calculation to find an UV RG fixed point to control the theory.
(4) A non-perturbatively non-renormalizable theory is the negative of the above.
Note that the continuum limit (a theory non-pertubatively defined to exist in the limit $\Lambda\to\infty$) is of little interest for most applications of QFTs, since in statistical physics and condensed matter there is always a finite UV cut-off, and in HEP, one can work with EFTs, sufficient to describe energies obtained in accelerators.
See also this post Why do we expect our theories to be independent of cutoffs?