How do you determine the Lagrangian? 
*

*I have always been puzzled by how do you arrive at Lagrangians? 

*That is, how do you know that the functional you need to get Newton's equations is 
$$L  =  T-V(x)~?$$

*Do you derive the Lagrangian first somehow or do you just guess the one which would satisfy the action to give equation's of motion? (because then you would need to know the equations of motion first.)

*Also, is the Lagrangian always equivalent to something resembling $T-V$, or there are other ways to determine it?

*More generally, is the action known before you know the equations of motion, or vice versa? 

*What I really wish to know is, was the Einstein Hilbert action discovered before field equations were? If so, how?

*My major doubt is how do you come across the Lagrangian if you don't know the equations of motion, and you can't guess $L$ then?   
 A: Not guessing at all. The action principle was discovered after Lagrange's equations of motion. So all you need to do is to arrive on it, from Newton's Laws. We know Newton's Laws in Cartesian coordinates. All we need to do them, is to convert it to generalized coordinates. So, let the definition of a generalized coordinate:
$$
q_k = q_k(x_i),\quad\quad
\dot q_k = \sum_i\frac{\partial q_k}{\partial x_i}\dot x_i\quad\quad
\delta x_i = \sum_k\frac{\partial x_i}{\partial q_k} \delta q_k
$$
Notice that for a kinetic energy of a single particle $K$:
$$
K = \frac{1}{2}m\dot x^2  \quad\Longrightarrow\quad
\frac{\partial K}{\partial \dot x} = m\dot x = p
$$
This also works with angular momentum when coordinate is theta. Hence, let's define a generalize momentum this way:
$$
p_k = \frac{\partial T}{\partial\dot q} =
\frac{\partial}{\partial\dot q}\sum_i\frac{1}{2}m\dot x_i^2 = 
\sum_i m\dot x_i\frac{\partial x_i}{\partial\dot q_k}
$$
This works in Cartesian coordinates, and polar coordinates, as giving linear and angular momentum. So, sounds a good definition. Now, let's define our generalized force $Q_k$ as the work done by a small displacement: 
$$\delta W = \sum_k Q_k\delta q_k = \sum_i F_i\delta x_i = 
\sum_i F_i\sum_k\frac{\partial x_i}{\partial q_k} \delta q_k\quad\Longrightarrow\quad
Q_k = \sum_i F_i\frac{\partial x_i}{\partial q_k}
$$
However, we know the potential energy and force are related:
$$
F_i = -\frac{\partial V}{\partial x_i} \quad\Longrightarrow\quad
Q_k = -\sum_i \frac{\partial V}{\partial x_i}\frac{\partial x_i}{\partial q_k}
= -\frac{\partial V}{\partial q_k}
$$
The derivative of momentum:
$$
\frac{dp_k}{dt} = \frac{d}{dt}\sum_i m\dot x_i\frac{\partial x_i}{\partial\dot q_k} = 
\sum_i\left(m\ddot x_i\frac{\partial x_i}{\partial q_k} + m\dot x_i\frac{d}{dt}\frac{\partial x_i}{\partial q_k}\right)
$$
This can be reorganized only in terms of generalized coordinates:
$$
\frac{\partial T}{\partial q_k} = \sum_im\dot x_i\frac{d}{dt}\frac{\partial x_i}{\partial q_k}\quad\Longrightarrow\quad
\frac{dp_k}{dt} = Q_k + \frac{\partial T}{\partial q_k}
$$
$$
Q_k = \frac{d}{dt}\frac{\partial T}{\partial \dot q_k}-\frac{\partial T}{\partial q_k}
$$
Now, since:
$$
Q_k = -\frac{\partial V}{\partial q_k}\quad\mbox{ and }\quad
\frac{\partial V}{\partial \dot q_k} = 0
$$
We can then write Euler-Lagrange equations:
$$
\frac{d}{dt}\frac{\partial V}{\partial \dot q_k} - \frac{\partial V}{\partial q_k} = \frac{d}{dt}\frac{\partial T}{\partial \dot q_k}-\frac{\partial T}{\partial q_k}
$$
If we set $L = T - V$, we have:
$$
\frac{\partial L}{\partial q_k} - \frac{d}{dt}\frac{\partial L}{\partial \dot q_k} = 0
$$
Since this is a typical equation of functional minimization, from here we can derive action principle, and so on. As you can see, there were no guesses.
