This actual reasons behind many statements you mentioned may be a bit different.
First, one doesn't need too much Chern-Simons handwaving to say that $c_L=24 k_L$ etc. The three-dimensional action of general relativity may be rewritten so that it only depends on $l/G$ where $G$ is Newton's constant (of dimension length) and $l$ is the curvature radius, so that $2/l^2$ is the cosmological constant term added to $R$ in the Einstein-Hilbert action.
Brown and Henneaux have studied the asymptotic action of the Virasoro group on the three-dimensional spacetime and from the commutators, they could simply determine that $c_L=c_R=3l/2G$. Now, $l/G$ is a multiple of 16 - it's plausible that one needs the Chern-Simons variables to argue this much (one uses the integer-valuedness of the levels). But the isomorphism between CS and GR works perturbatively.
Also, if $c_L$ and $c_R$ differ, it's still true that $c_L-c_R$ must be a multiple of 24 for any CFT - not just CFTs that are the duals of some AdS space. This follows from the $\tau\to\tau+1$ modular transformations of the torus - or, equivalently, from the requirement that $L_0-\tilde L_0$ has to be integer-valued for physical states (the implication holds because the ground states have energies $-c_{L,R}/24$).
It just happens that when you translate the levels of the Chern-Simons theory to the ground state energies of the boundary CFT, they're equal up to the sign. A necessary condition for holomorphic factorization of a CFT is that the ground state energies for the left-movers and right-movers are two integers - which naturally translates to the integrality of the levels.
Witten kind of assumed it was also a sufficient condition - i.e. that one can find a dual description with a monster symmetry not only for $k=1$ which is what he did but also for $k=2,3,\dots$. This naturally sounding conjecture was disproved, at least for $k=2$, by Davide Gaiotto by some representation theory of the monster group:
http://arxiv.org/abs/arXiv:0801.0988
It seems pretty likely that the theories with the monster group symmetry don't exist for any higher $k$, either. It may still be the case that the higher $k$ CFT duals exist and have a smaller sporadic symmetry - much like the ABJM at a general level generalizes the BLG construction but reduces its symmetry.
Various 2D CFTs may have AdS duals but they won't be pure gravity: they will include some massless bulk states i.e. marginal deformations. The Leech-lattice-based models that Witten studied were special because the Leech lattice doesn't produce any massless states - it only produces massive states which may be interpreted as black hole microstates. Witten hasn't discussed those in his paper. So he was not saying that non-factorizable CFTs can't have an AdS dual: they just can't have a pure gravity AdS dual in three dimensions.
