What kind of Lagrangians can we have? In any physics book I've read the Lagrangian is introuced as as a functional whose critical points govern the dynamics of the system. It is then usually shown that a finite collection of non-interacting particles has a Lagrangian $\frac{1}{2}(m_1\dot{x}_1^2 + \cdots + m_n \dot{x}_n^2)$. It is then generally argued that $L=T-U$. I feel like something is missing here. 
What exactly are the physical hypotheses that go into this? Can we have other forms of the Lagrangian? How do we know those are "right"? Do we always have to compare them to the form of the equations we derived previously? For example, the Lagrangian formalism seems to be justified usually in so far as it 'works' for a finite collection of particles. Then you can solve any dynamics problem involving a collection of particles.
I have been vague so let me try to be more precise in my question.
Is the principle of least action an experimental hypothesis? Is it always true that $L=T-U$? When we don't know what the Lagrangian is, do we have to just guess and hope it is compatible with the dynamical equations we had already? Or can we perhaps start with the ansatz of a Lagrangian in some cases?
I hope this is sufficiently precise.
 A: Let me comment on your second question:

When we don't know what the Lagrangian is, do we have to just guess and hope it is compatible with the dynamical equations we had already?

If you want the variational derivative of your Lagrangian to yield your equations of motion
(or a system which is equivalent to your equations of motion) you should solve 
the inverse problem of calculus of variations (googling will land you plenty of references; for the "mechanical" case which is apparently your primary interest, you can start here; see also this book by Ian Anderson and Gerard Thompson). In general, there are certain necessary conditions for your equations of motion to satisfy in order that the Lagrangian exists at all. If these are satisfied, finding the Lagrangian $L$ essentially boils down to using an appropriate homotopy operator to reconstruct $L$ from its variational derivative, see e.g. Ch. 5 of the book Applications of Lie groups to Differential Equations by Peter Olver.
As a historical remark, it is interesting to note that one of the first Fileds medalists, Jesse Douglas, has made significant contributions to this field of research.
Sorry for being rather sketchy, maybe I'll expand this answer a bit later.
A: This question has a very wide scope, judging by the comments which have appeared already.  I will try to narrow the scope a little in my answer.
Classical mechanics is all about how a system evolves in time.  The system itself is defined by specifying a configuration space, which we take to be a smooth manifold $M$.  (The coordinates in the configuration space are usually known as "generalized coordinates" in the physics literature, to distinguish them from the standard coordinates in $\mathbb{R}^n$.)  A lagrangian is then simply a differentiable function $L: TM \to \mathbb{R}$ on the tangent bundle.  Relative to local coordinates $(x,v)$ for $TM$ (where $x$ --- the "positions" --- are local coordinates on $M$ and $v$ --- the "velocities" --- are the fibre coordinates), the lagrangian $L$ determines the equations of motion via the principle of least action, which results in the Euler-Lagrange equations:
$$
\frac{d}{dt} \frac{\partial L}{\partial v} = \frac{\partial L}{\partial x}
$$
evaluated on curves $(x,\dot x)$.  In addition one would like the fibre derivative $\frac{\partial L}{\partial v}$ to be nondegenerate, so that we get a fibrewise isomorphism $TM \to T^*M$.  Then $p = \frac{\partial L}{\partial v}$ are the canonical momenta and nondegeneracy means that we can invert this relation and write $v$ as a function of $p$.  The hamiltonian $H : T^*M \to \mathbb{R}$ is defined as the Legendre transform of the lagrangian
$$H(x,p) = p v - L$$
where $v$ is given as a function of $p$.  The cotangent bundle $T^*M$ has a natural symplectic form $\omega$ and the hamiltonian vector field associated to $H$ defines a flow which evolves the state $(x,p)$ in the same way as do the Euler-Lagrange equations.
In general there is no canonical way to choose $L$ (or $H$): it ultimately depends on the physical system one is trying to model.  Of course, we have had so much experience, that there are many heuristics one can use to guess the appropriate lagrangian.  In doing so, symmetries play an important rôle and nowhere is this more evident than in the business of "model building" in particle physics.  Here we are dealing with field theories, whence the configuration space consists of sections of certain homogeneous vector (or more general fibre) bundles on the spacetime and there are a number of symmetries (both Lie and discrete) that one might want our lagrangian to have.
More interesting perhaps are the theories for which no lagrangians are known, or at least no lagrangians which are manifestly invariant under the desired symmetry.  There are many examples of such theories, some very interesting ones in six dimensions which are intimately linked to the geometric Langlands program as described in this paper of Witten's, for istance.
A: As far as the priniciples are concerned that enter the choice of a Lagrangian it is important to distinguish between classical systems and quantum systems. In the case of classical particle systems, or classical field theories, the primary input has historically been the dynamics of the system, as encoded in the equations of motion. The choice of Lagrangian, or rather the class of equivalent Lagrangians, then is determined by the constraint that the variational principle needs to reproduce this known dynamics. In the case of quantum field theories the strategy is somewhat different, and Feynman's approach to the computation of physical observables via the path integral puts more emphasis on the Lagrangian as the fundamental quantity. Here a powerful guide are symmetries that constrain the possible forms of the Lagrangian. Generally, symmetries are not enough to determine its form, and more experimental constraints are necessary to specify the theory. The final justification of any given Lagrangian is that its physical consequences are  consistent with the observed phenomena. 
A: I believe the standard answer to your question is that if one starts from Newton's Laws of Motion for a system of particles, then the second law says essentially $F = Ma$, giving the equations of motion as a second order ODE that is completely determined if we know the forces between particles. Then, and this is the important point that is often un-appreciated, Newton's Third Law (action and reaction are equal and opposite) IMPLIES that the forces are derivable from a potential function $U$. [The latter statement is WRONG ! See the comments and correction below.] It then follows by easy formal manipulation that $F=Ma$ is equivalent to the Euler Lagrange Equations for the Lagrangian $L= K - U$ where the kinetic energy $K$ is given by the formula you gave above for the Lagrangian without interactions. If you are interested in further details, I have a recent book (published by AMS and co-authored with my son Robert) called "Differential Equations, Mechanics, and Computation" in which I go to great lengths to give a conceptual approach to exactly the sort of question you are asking. There is a companion website at http://ode-math.com/ at which you can download more than half the material in the book as pdf files.
A: "Is the principle of least action an experimental hypothesis?" A physicist views classical mechanics as a semiclassical limit of quantum mechanics, valid in the limit that $\hbar \rightarrow 0$. In the path integral approach to quantum mechanics one studies integrals over an infinite dimensional space of paths (yes,yes I know these are not completely rigorous) of the form $\int {\cal D}x e^{i S[x]/\hbar}$ with $S= \int {\cal L} dt$ where ${\cal L}$ is the Lagrangian of the system. The principle of least action can then be viewed as a stationary phase approximation to the path integral, valid in the semiclassical limit. Thus rather than a hypothesis I would say the principle of least action is derived as part of the process of taking the classical limit of quantum mechanics.
A: Here are two   nice, natural, examples of Lagrangians not of the form $T-U$
which occur naturally in  physics.
For a relativistic particle of charge e, mass m, travelling under the
influence of an electromagnetic field F, with one-form potential A (so
$F = dA$),  the Lagrangian is
$L = mds - eA$ where $ds$ is the proper time, or element of arc-length in 
Minkowski space (or more generally, the space-time within which said particle is
travelling). [References: Feynman, vol. II, p. 19-7;  Folland
`Quantum Field Theory: A tourist's guide, ch. 2, p. 29. Most intermediate
level physics texts] This can  be parsed so as to have the form $L(q, \dot q)$ in
two different ways.  Way 1: choose an arbitrary parameter $u$ for the
time and parameterize the space-time path with $u$.  Then the $\dot q$ 
is $dq/du$.  Way 2: choose to parameterize with time, which in one of the
space-time coordinates.  The non-relativistic limit of this $L$ is the $L$
of Alex R.s answer.  (This  variational principle is particularly interesting for photons,
where $ds = 0$.)
The oldest variational principle in mechanics (excluding Fermat's for optics) is that attributed to Maupertuis. He says that   solutions to Newton's equations at
fixed energy E, extremize $L = \sqrt{(E-U)T}$, using your terminology above.
This Lagrangian represents a metric conformal to the Euclidean metric, as represented
by $T$. (The geodesic time of these extremals is not Newtonian time.) 
I agree with Moduli that symmetry is one of the key ingredients that
goes into the choice of a Lagrangian. In the symmetry light, 
it is worth noting that the  two above Lagrangians are homogeneous
of degree 1 in `velocities', so   invariant under reparameterization
of paths. 
A: The most valuable discovery of the 20th century physics is symmetry. When you try to write down a Lagrangian for a system, usually there are two "principles": (1) the symmetries this system has and (2) experience. So no, L is not always T-U. For example, in General Relativity the Lagrangian (or rather Lagrangian density) is R, the scalar curvature of the spacetime manifold. As another example, in WZW models, the Lagrangian has two parts: a "kinetic" term plus a Wess–Zumino term. 
It is in quantum field theory that all kinds of Lagrangians pop up. What is more interesting is that the best you can do is to write down an “effective Lagrangian” at a certain energy scale, which may (and usually does) get quantum corrections at higher energy scales.
A: The Lagrangians in physics usually take the form $L=m\dot{x}^2/2+...$ (or $\mathcal{L}=(\partial \phi)^2/2+...$ in field theory), i.e. the velocity dependence is quadratic.
An important consequence of this form can be seen in the path integral formulation of quantum mechanics. The amplitude as a path integral in the phase space is $\int \mathcal{D}x \ \mathcal{D}p \ e^{i\int(p \ dx - H \ dt)}$ where the Hamlitonian $H$ is a function of $p, x$ and $t$. The thing is, this amplitude is in general NOT equal to the form we usually use $\int \mathcal{D}x \ e^{i\int L \ dt}$. The two forms are equal when $H$ depends on $p$ as $p^2$, i.e. when $L$ depends on $\dot{x}$ as $\dot{x}^2$. (the derivation can be found in Polchinski, Peskin etc., basically $e^{ip^2}$ will give a constant by Gaussian integration)
I am not sure if this is the reason that physical Lagrangian must take the form $L=m\dot{x}^2/2+...$, but at least I feel this shows some deep connection between the Lagrangian formulation and Hamiltonian formulation in quantum theory.
A: As a theoretical physicist who shifted to pure mathematics, I think to answer this question and as a clarification to previous posts, we should not forget the historical side of the evolution and origins of the terms involved in physics theory modeling.
The origin of the principle of stationary ('least' most of the time) action comes as a variational formulation using a functional $S[q(t)]:=\int_{t_1}^{t_2}L(q^i (t),\dot{q}^i (t);t)dt$ for the Lagrange equations of the real motion of a system with generalized coordinates $q^i (t)$ (obtained this way they are called Euler-Lagrange equations): 
$$\delta S[q_{real}(t)]=0\Rightarrow \frac{d}{dt}\frac{\partial L}{\partial \dot{q}^i}-\frac{\partial L}{\partial q^i}=0$$
The original Lagrange equations of motion were obtained as a reformulation of Newton's second law of mechanics for the case of generalized coordinates (the remaining degrees of freedom after introducing constraints) as an easier to handle version of D'Alembert's principle. D'Alembert wrote the 'virtal work' principle as a way to state a general equation for statics, which in a way amounts to postulate that constraint forces do not exert work  (as they should be internal and the weak 3rd law applies). Now given Newton's second law for a system of particles, D'Alembert reformulates constrained dynamics as statics introducing the inertial force (you can see details at wikipedia) $$\sum_i (\vec{F}_{i}^{ext}-\frac{d\vec{p}_i}{dt})\cdot\delta \vec{r_i}=0$$
Lagrange wanted to work only with generalized coordinates which changing variables in D'Alembert's principle led him to the original Lagrange's equations of motion in terms of a kinetic generalised energy $T$ and generalized forces $Q_i$; furthermore he absorbed those conservative forces which derived from a potential $Q_i^c=-\partial U/\partial q_i$ (or more generally those which even depended on speed or time but had the required form of the left-hand side) along with the kinetic energy, into a function $L=T-U$ now called the Lagrangian $$\frac{d}{dt}\frac{\partial T}{\partial \dot{q}^i}-\frac{\partial T}{\partial q^i}=Q_i\Rightarrow \frac{d}{dt}\frac{\partial L}{\partial \dot{q}^i}-\frac{\partial L}{\partial q^i}=Q_i^{no-c.}$$
That is the origin of the form of the lagrangian as $L=T-U$. Now, the non-conservative forces $Q_i^{no-c.}$ appear because we are considering general 'open systems' which interchange energy with their enviroment, other systems as sources of energy, etc. To check this form in detail, first consdier that a closed system is always of the form $L=T-U$ because of a constructive reasoning as follows. For a free particle, at least locally, because of the homogeneity of space and time, and isotropy of space, we must have $L(q_i,\dot{q}_i;t)=T(v^2)$, that is a scalar which only depends on the particle and its speed (but no direction); since a free particle must still be free in another inertial system by def. the relation must be linear $L=a\cdot v^2$ (this is because any other Lagrangian giving the same equations of motion has to be of the form $L'=A\cdot L+\frac{d}{dt}\Omega(q;t)$ for which an inertial transformation $\vec{v}'=\vec{v}-\vec{\epsilon}$ must imply at first order $-2\vec{v}\cdot\vec{\epsilon}\partial L(v^2)/\partial (v^2)\propto d\Omega(q;t)/dt\Leftrightarrow \partial L/\partial (v^2)=0$); now the constant $a$ characterizes the particle, and must reduce to the free Newtonian second law ($p_i=m\cdot v_i =0$) therefore $a=m/2$. For a system of free particles without interactions the same applies summing over the individual kinetic energies $L_{free}=T=\frac{1}{2}\sum_i m_i v_i^2=\frac{1}{2}\sum_{i,j} A_{ij}\dot{q}^i\dot{q}^j$ (when $T$ is a cuadratic form the system is called 'natural' which happens when $\partial \vec{r}_k(q^i(t),\dot{q}^i(t);t)/\partial t = 0$ for all particles $k$, common for the natural case of constraints not dependent on time). To add interactions between particles in a closed system, their degrees of freedom must be coupled, which just means that the relative energies are not lost to the exterior, and this is satisfactorily implemented by a potential function $U=U(q_i,\dot{q}_i)$. By this method we obtain a general framework for mechanics using Lagrange's equations: postulating different potentials we obtain different models of interactions which shall be contrasted with experiment to constrain the form of $U$ (this may be done to obtain just effective phenomenological models, nevertheless all fundamental interactions of physics seem to fit this framework very well). Finally, when part B of the system A+B is fixed (like considered external) its motion can be treated like already 'solved', which opens the previous closed system, separating some of the degrees of freedom $q_B^i(t)$; therefore the Lagrangian decouples $L_{open}=T_A+T_B(\dot{q}^i_B(t))-U(q_A,q_B(t),\dot{q}_A,\dot{q}_B(t))$, in this case $T_B=d\Omega(q_B,t)/dt$ for some $\Omega$, so we can neglect that part since does not contribute to the equations of motion and therefore $L_{open}=T_A-U_{open}(q_A,\dot{q}_A,t)$. This way $U$ creates the effect of non-conservative forces which are just those that add or subtract energy from the system without taking into account where this energy goes.
Therefore we can consider the Lagrange equation (without non-conservative forces) as the general more fundamental equation given individual interactions between the particles of the Universe, at least in principle. This is why the form $L=T-U$ is the usual approach in theoretical physics to deal with dynamics, since the very concept of instantaneous force at a distance à-la Newton is anti-natural (above all after special-general relativity) and the energetic local approach is not only mathematically better but philosophically more satisfactory. The Hamiltonian approach can be taken also as a starting point, or as a Legendre transformation of Lagrange dynamics, but that way one makes a non-relativistic break down of the coordinates $x^i, t$ which is useful for non-relativistic quantum mechanics.
Now in general, physics is a theory of fields so we want to add these to the framework. This is easily done by considering them as continuous systems of degrees of freedom, providing generalizations of kinetic and potential energies of those. 
Furthermore one wishes for a (special or general) relativistic invariant theory which forces the $Ldt$ to be a Lorentz scalar in order to get Lorentz-covariant ($SO(3,1)$) equations of motion (i.e. covariant as tensor equations in a pseudo-Riemannian manifold). This way the free case reasoned above leads us to $ds=Ldt$ (where $ds$ is the relativistic space-time interval or 'proper time' measured by the particle) which indeed reduces to $ds\approx \frac{1}{2}mv^2$ for speeds $v\ll c$, and therefore can be taken as a relativistic generalization of the framework. Nevertheless point-particles are idealizations and both the classical and quantum theories require a field-theoretic treatment of matter (in the classical case, particles appear as small density lumps, and in the quantum case particle behaviour arises for discrete-like energy levels of the quantum field states). In the wikipedia article about Lagrangians different examples can be seen from point particles to fields, their kinetic terms and so on.
In any case, the traditional form $L=T-U$ has its roots in the very nature of mechanics and any modern field theory is created by building up possible $T-U$ functionals from the field's degrees of freedom, i.e. the fields $\phi_a(x^\mu)$ and their "velocities" $\partial \phi_a/\partial x^\nu$ (for relativistic invariance reasons time-like speed $\frac{\partial}{\partial t}$ is not enough and the whole $\partial_\nu$ must be used). Hence one constructs kinetic terms like (Einstein's summation convenction) $T_\phi=\frac{1}{2}\partial_\mu\phi_a\partial^\mu\phi_a$ for scalar fields or $T_A=F_{\mu\nu}F^{\mu\nu}$ for vector fields ($F_{\mu\nu}:=\partial_\mu A_\nu-\partial_\nu A_\mu$ is in this case the tensor constructed from the field used to define its kinetic energy because we want to build invariant 'speed-like' $\partial_\mu$ scalars that are as well Gauge invariant which is another physical symmetry typically required besides Lorentz; furthermore, requiring gauge invariance for different Lie groups, tyipcally $SU(N)$, one forces the automatic appearance of fields and couplings between the matter fields responsible for the interactions, which is just working with connections and curvatures of fiber bundles). Since any term which makes the field equation of motion non-homogeneous is considered a source of perturbation, or force, one sees the corresponding couplings in the Lagrangian like a potential energy, giving as always $\mathcal{L}=T_\phi+T_A-U(A_\mu,\phi)$. With this, the coupled physical equations of motion are deduced for the principle of stationary action, where now the integration must be over the whole space and an interval of time (i.e. $\mathcal{L}$ is a density), the field Euler-Lagrange equations of motion:
$$\partial_\mu\frac{\partial\mathcal{L}}{\partial (\partial_\mu\phi)}-\frac{\partial\mathcal{L}}{\partial\phi}=0$$
Finally these equations give the solutions of motion, that is the real field configurations at any point in space-time, which contribute the most in a quantum-theoretic framework, where one weighs complex transition amplitudes by Feynman operational methods using the action for each possible field-configuration ('motion'): $e^{\frac{i}{\hbar}S[\phi,A_\mu]}$. As remarked in other comment, the semi-classical approximation $\hbar\rightarrow 0$ makes the classical solution of Euler-Lagrange the predominant one, hence deducing the principle of stationary action. (Also, in the non-relativistic hamiltonian quantum-mechanics Ehrenfest's theorem provides a classical Newton-like equation of motion for the average degrees of freedom)
Indeed as science makes progress we must see previous theories and models as limiting cases of new more precise theories, but in the beginning any physical theory must be constructed by physical insight, intuition and permanent comparison with experiment. Even though Feynman titled his thesis that way, he does not develop his approach to quantum theory starting from the action-principle, on the contrary he works with standard (hamiltonian) quantum mechanics and obtains a novel method for computing quantum probability amplitudes in which the classical action appears. You could start with quantum mechanics as an axiomatic system, develop Feynman's approach to quantum propagators of motion and deduce that classical approximate solutions of motion must obey, at first order of quantum corrections, the classical Euler-Lagrange equations of motion. At the same time, you need the input from the experimentally succsessful classical mechanics to get to quantum mechanics... and so forth. In the end at any moment of time in the history of science we are getting better and better mathematical structures that model reality to different degrees of precision; the important point is that a new one must contain an old one as an approximation in some regime, and explain even more. This way, theoretical physics tends to get better structures to encompass more phenomena from Nature in a simpler and simpler manner as it explains more effective laws with less theories (currently almost all the phenomena observed is explained by general relativity and quantum field theory, and unifying both is the neverending quest for the holy grail of physics).
A: Is $L=T-V$ ?
Depends what you mean by "$V$". Try finding $V$ for a system with nonconservative forces. There's a sleight of hand here of course, since when we talk about $V$ we really mean $V=V(q)$, a function of the coordinates $q$. This doesn't mean we can't find a Lagrangian. Take electromagnetism for example, say a charged particle moving through an electromagnetic field. It's lagrangian can we written as:
$L=\frac{1}{2}m\dot{\mathbf{q}}^2-e\phi(\mathbf{q},t)+e\dot{\mathbf{q}}\cdot \mathbf{A}(\mathbf{q},t)$
where $\phi$ and $\mathbf{A}$ are the scalar and vector potentials respectively. How did we get this Lagrangian? One way is working backwards from the Lorenz force $\mathbf{F}=e\left(E+\frac{1}{c}\mathbf{v}\times\mathbf{B}\right)$, which gives us the equations of motion, and then we go back to our course in electromagnetism to remember that electromagnetism comes from scalar and vector potentials. 
If you are handed the equations of motion of a system (EOM), then there can be multiple Lagrangians that give rise to these EOM. In fact, at least locally, when two Lagrangians $L_1,L_2$ give rise to the same EOM, then $L_1-L_2=d\Phi/dt$, where $\Phi$ is a function on the position coordinates $\mathbb{Q}$. The point is, if you already have equations of motion, then finding a Lagrangian becomes a derivative matching game. 
A: Here are two   nice, natural, examples of Lagrangians not of the form $T-U$
which occur naturally in  physics.
For a relativistic particle of charge e, mass m, travelling under the
influence of an electromagnetic field F, with one-form potential A (so
$F = dA$),  the Lagrangian is
$L = mds - eA$ where $ds$ is the proper time, or element of arc-length in 
Minkowski space (or more generally, the space-time within which said particle is
travelling). [References: Feynman, vol. II, p. 19-7;  Folland
`Quantum Field Theory: A tourist's guide, ch. 2, p. 29. Most intermediate
level physics texts] This can  be parsed so as to have the form $L(q, \dot q)$ in
two different ways.  Way 1: choose an arbitrary parameter $u$ for the
time and parameterize the space-time path with $u$.  Then the $\dot q$ 
is $dq/du$.  Way 2: choose to parameterize with time, which in one of the
space-time coordinates.  The non-relativistic limit of this $L$ is the $L$
of Alex R.s answer.  (This  variational principle is particularly interesting for photons,
where $ds = 0$.)
The oldest variational principle in mechanics (excluding Fermat's for optics) is that attributed to Maupertuis. He says that   solutions to Newton's equations at
fixed energy E, extremize $L = \sqrt{(E-U)T}$, using your terminology above.
This Lagrangian represents a metric conformal to the Euclidean metric, as represented
by $T$. (The geodesic time of these extremals is not Newtonian time.) 
I agree with Moduli that symmetry is one of the key ingredients that
goes into the choice of a Lagrangian. In the symmetry light, 
it is worth noting that the  two above Lagrangians are homogeneous
of degree 1 in `velocities', so   invariant under reparameterization
of paths. 
