Do "typical" QFT's lack a lagrangian description? Sometimes as a result of learning new things you realize that you are incredibly confused about something you thought you understood very well, and that perhaps your intuition needs to be revised. This happened to me when thinking about non-Lagrangian descriptions of QFT's. Below I'll provide a brief description of my intuition and why I think it's been challenged, but for the sake of clarity here is my question: do ''typical" or "generic" QFT's have Lagrangian descriptions? How can one quantify the size of the set of QFT's with and without Lagrangian descriptions? When a QFT is said to not have a Lagrangian descriptions, does this mean it really does not have one, or only that such a description is difficult or impossible to find?
As a young student of QFT, I studied the Wilsonian approach to RG and it left me with a very simple and geometric understanding of field theory. To describe some physical process as a QFT, one first has to understand the symmetries of the problem (such as Poincare symmetry, gauge and global symmetries). Then one writes down a general polynomial Lagrangian consistent with these symmetries. As an example, consider the case of an $O(n)$ scalar field $\vec{\phi}$ (and let's restrict to Lagrangians with the standard, two derivative kinetic term just for simplicity):
$ \mathcal{L} = -\frac{1}{2} (\nabla \vec{\phi})^2 + a_2 \vec{\phi}^2 + a_4 \left( \vec{\phi}^2 \right)^2 + a_6 \left( \vec{\phi}^2 \right)^3 + ...$
From Wilsonian RG, I'm used to thinking about the space of possible field theories (with the symmetry restrictions imposed above) as corresponding to the infinite-dimensional parameter space $a_2, a_4, a_6, ...$. A point in this space specifies a Lagrangian and defines a field theory. RG flow is simply represented as a trajectory from one point (in the UV) to another (in the IR). Many different starting points can have the same endpoint, which allows a simple pictorial description of universality classes to be drawn.
So from this logic I would think that all QFT's admit Lagrangian descriptions, but some of them might require an infinite number of interaction terms. This intuition was challenged by reading about CFT's and gauge/gravity duality. In these contexts  Lagrangian descriptions of the field theory are almost never written down. In fact, according to generalized gauge/gravity (i.e. the belief that gravity with AdS boundary conditions is dual to some CFT), it might seem that many QFT's do not admit Lagrangian descriptions. This generalized gauge/gravity should work just fine in $D=100$, and the UV fixed point field theory certainly doesn't admit a simple Lagrangian description since in sufficiently high dimension all the interaction terms are relevant (and therefore negligible in the UV), which would suggest that the UV fixed point is simply free, but that of course is not the case.
I arrived at this confusion by thinking about AdS/CFT, but I'd be very happy to simply have a strong understanding of what exactly it means for a QFT to not have a Lagrangian description, and a sense for how "typical" such theories are.
Edit: And let me add a brief discussion on CFT's. From the bootstrap approach to CFT's, one starts with CFT "data", i.e. a set of conformal dimensions and OPE coefficients, and then in principle one should be able to solve the CFT (by that I mean calculate all correlation functions). So here is an entirely different way of characterizing field theories, which only applies for conformal theories. Non-CFT's can be obtained by RG flowing away from these fixed points. It would be helpful to understand the connection between this way of thinking about general QFT's and the above Wilsonian one.
 A: From my reading of your question, you seem to have confused what we actually mean by the Wilsonian approach, a QFT and a Lagrangian density, so I'll hopefully deal with them in turn and I hope it helps. 
The Wilsonian approach to QFT can be used to do two things, the first is the more used and applied case in the particle physics which is to find the RG flows of the coupling constants which in turn reduces (or get rid of) divergences in the theory by allowing weakening coupling at higher energies and thus reducing the effect of loop corrections. The other use, which is what I use the Wilsonian technique for, is EFTs. This is the process of integrating out higher order corrections in the theory and then using a polynomial expansion to approximate the Lagrangian of the action. Both processes are ultimately the same, just with a different outcome. In the former case we absorb all the extra terms into the RG flows and in the latter case we admit local contact terms into the theory which expresses the high energy contribution to low energy behaviour. Thus if a Lagrangian is admitting an infinite number of terms then it is likely an EFT.
This then leads on to your questions about gravity and "typical" QFTs. In the case of gravity, most of the calculations we do use an EFT of some kind or another (there are exceptions but they are not QFTs in the strictest sense of the meaning). We use the EFT because we can explore low energy corrections to gravitational behaviour on a static background without ignoring higher energy effects. HOWEVER, in the gravity case we actually write the EFT down first and then use that, and that is because we have no UV complete theory of gravity and so we can only be certain that the EFT is correct. Currently there are efforts being made by researchers at Imperial College to try and use EFTs and S-Matrix postulates to obtain some knowledge of the full UV complete action (it is worth a google). Thus if a QFT doesn't have a Lagrangian it may just be that it's UV complete Lagrangian doesn't exist and that writing anything else down would be confusing and pointless.
The other argument would be that in QFT the fundamental theory should not be written in terms of a Lagrangian but in terms of an action since usually this is the only gauge invariant quantity we can write down. The Rarita-Schwinger free field is an example of this. Thus the Lagrangian approach is actually quite rare when thinking about more complicated QFTs because they simply do not have the properties we require to use them, what's more they often become ill defined on non-static (or nearly non-static) space-times because they have no well defined metric evolution without the measure of the action. Hence these theories require the explicit application of the variation principle in order to uncover their physics.
So, in short, a "typical" QFT does not have a Lagrangian because the universe is just too complicated. We can only really work with actions and EFTs, that being said simple systems do have Lagrangian which will admit a Lagrangian treatment but CFTs are not such a system. 
A: I'd say a minimalistic requirement for a QFT would be the possibility of defining and computing in some way the S-matrix (maybe with unitarity: for instance you may relax locality, local-Poincarè invariance and maybe microcausality).
If you can define the quantum fields of your theory in the setting you work (the commutation relations might give you a hard time depending on how much you relax the standard assumptions) then you should be able to get to the Lagrangian by seeing it as the generator of the operators that appear in the theory (through the relaxed versions of the time evolution or the path integral).
These operators could be read from the S-matrix with some freedom in their definitions: you could take every correlator as a different operator or you could come up with a subset of operators that generates all the others. These operators (or some resummation of some of them) may be non-local or evade the standard Lagrangian requirements (renormalizability for instance).
Now however note that in standard QFT your background should be a stationary point of the action, i.e. satisfying the Euler Lagrange equations for a classic Lagrangian. The prior knowledge of a "classical" Lagrangian from which the background arises is relevant as it amounts to being able to reformulate your problem with the vacuum as a background. It should generally be possible to deal with this relaxing the standard assumptions (in particular here I'm thinking to having a scalar Lagrangian); the other contributes to the Lagrangian coming from the inspection of the S-matrix will be corrections to the "background Lagrangian".
The behavior of the theory under change of energy scale should be included in the S-matrix to begin with.
In conclusion my impression is that there may be situations in which defining fields and their commutation relations is difficult and prevents a standard Lagrangian treatment even thought you are able to define operators and correlators.
I hope this point of view can help you clarifying your doubts.
