Is the Lagrangian approach essentially a 'theory of everything'? From learning about the Lagrangian lately it seems that that it can underlie so many phenomena that it must be the unifying concept that underpins all physics. I often hear that physicists are searching for the theory of everything, why is the Lagrangian approach not considered to be such a theory?
On a related note, can the Lagrangian (and/or) Hamiltonian approach to describing a system be considered the ultimate test of validity for any physical theory? In other words, is it necessary that every fundamental physical theory can be derived using the Lagrangian approach?
 A: The Lagrangian is just a mathematical tool, it does not contain any physical theory without an experimentally determined Lagrangian.
You're confusing a framework with a theory. Inn Classical Mechanics, we use the Lagangian $L = T - V$ because it happens to work there, while EM, Gravity and particle physics have their own Lagrangians to describe different phenomena. Trouble is, there's no deeper answer to why the Lagrangian takes the form it does than "because it works" - physics is, after all, an experimental science. Theorists work on making up new Lagrangians (in practice, often educated guesses) and the models that correspond most closely to experimental results are taken as the current theory.
In other words, you could make up a Lagrangian like $L = T + \pi*V - \phi$, where $\phi$ is the electric potential, apply Lagrange's equations, calculate the action and so on, but it's complete garbage – without the 'correct' Lagrangian, the mathematics is utterly meaningless. The physics in this framework is entirely contained in the properties of $L$.
A: The Lagrangian and Hamiltonian approaches are frameworks, and not theories. It is certainly true that a wide variety of systems are susceptible to such an approach.
However, there are many theories which do not possess Lagrangians. For example, it is believed that a certain set of six-dimensional superconformal field theories may be able to describe all lower dimensional conformal field theories. However, currently, there is no Lagrangian known for any of them. In addition, in certain conformal field theories, we may use a bootstrap approach to define the theory in terms of the algebra of its operators, the CFT data, without mentioning a Lagrangian.
Furthermore, there is currently no known Lagrangian for M-theory, though there is a matrix model which is believed to be M-theory in a certain limit (see work by Susskind).

Locality and Manifest Unitarity
There is also a known issue emerging with the Lagrangian framework itself, or at least its present implementations. In particular, quantum field theory is normally done in such a way as to make locality and unitarity manifest.
One of the consequences of this is that scattering amplitudes computed in this formalism using Feynman diagrams are much more complicated than their final expressions.
We also cannot currently construct a Lagrangian in a way to make Lorentz invariance manifest without introducing gauge redundancies. Thus, the present formalism is not without its flaws, and there are new formalisms emerging. For example, in the case of graviton scattering, it has been shown that the S-matrix may be constructed by seeing it as offering a representation of the BMS group. This is shown to lead to Weinberg's soft theorems and sub-leading soft theorems.
It would be reasonable to guess that should a 'theory of everything' be constructed, it may not be a standard quantum field theory as we understand it, and points that I mentioned above, especially in the modern literature into scattering amplitudes, hint at this.
