Least Action in General Relativity For an affinely parameterised geodesic we can form the Lagrangian:
$$
\mathcal L = g_{ab}\dot x^a\dot x^b = \text{constant}
$$
The Lagrangian is constant by the fact that the geodesic parallel transforms it's tangent vector, $\dot x^a$, thereby preserving it's length. My question in then this: If the Lagrangian is constant, what meaning can assign to the principle of least action? For a non varying Lagrangian surely the action will not vary with trajectory?
 A: OP's Lagrangian is indeed constant on-shell, but not necessarily off-shell. In contrast, the principle of stationary action compares various possibly off-shell paths.
A: You could ask the same exact thing for the Lagrangian of a nonrelativistic particle. It's an exactly analogous situation.
$$
L = \frac{1}{2} m \dot x^2
$$
Now, if we differentiate the Lagrangian with respect to time, we get
\begin{align}
\frac{d}{dt} L &= \frac{1}{2} m \frac{d}{dt} \dot x^2 \\
&= m \dot x \ddot x \\
&\neq 0
\end{align}
It's not $0$. For instance, if we plug in the trajectory
$$
x(t) = A \sin(\omega t)
$$
then
$$
\frac{d}{dt} L = m \dot x \ddot x = - m A^2 \omega^3 \sin(\omega t) \cos(\omega t) \neq 0
$$
just to give one example.
However, the equation of motion which comes from this Lagrangian is
$$
\ddot x \approx 0.
$$
Here, the squiggly equals does not mean "approximately" equals, but it means equal "on solutions to the equations of motion." So if you take a path $x(t)$ which extremizes the action, then the second time derivative of $x(t)$ is $0$. However, this isn't true for any random path, like $A \sin(\omega t)$!
Now, using $\ddot x \approx 0$, we get
$$
\frac{d}{dt} L = m \dot x \ddot x \approx 0.
$$
So, using our new notation, we see that, while $d L/dt$ is not identically $0$, it is equal to zero on solutions to the equations of motion. So $L$ is constant on solutions to the equations of motion, but it's not a constant in general. This distinction is very important. The action principle which comes from $L$ is therefore perfectly well defined.
A: 
For a non varying Lagrangian surely the action will not vary with trajectory?

The basic confusion is "constant in time" versus "constant over trajectories". The action is the time integral of the Lagrangian, and is a "functional" mapping an entire (hypothetical) trajectory to a number. Even if every trajectory had a constant-in-time Lagrangian (which isn't the case -- see other answers), that doesn't mean that the action is the same for every trajectory.
For example, in a given reference frame in flat spacetime, compare two trajectories between spacetime points A and B: motion at a constant speed along a straight line and motion at a (higher) constant speed along a curve (the speed has to be higher to reach point B following the longer path). The Lagrangian, and thus the action, will be greater in the second case even though the Lagrangian happens to be time-independent in both cases. Thus, it is meaningful to say that the straight-line trajectory has the least action.
A: Consider $L= x^2 + y^2 = \text{C} \to \delta L=\frac{\partial L}{\partial x}dx + \frac{\partial L}{\partial y} dy=0\to\frac{dx}{dy}=\frac{-y}{x} \\ \to x=\cos(\theta) \text{ & } dx=-\sin(\theta)d\theta \text{ and }  y=\sin(\theta) \text{ & } dy=\cos(\theta)d\theta.$
$L$ is constant but it's possible to find equations for $x$ and $y$ by varying $L$.
$L=g_{ab}\dot{x}^a\dot{x}^b =\text{C}$ only says, in this context, that the tangent vector has constant magnitude. The paths $x(s)$ and the space $g_{ab}$ are variable. Again, you can find how L behaves by differentiating it.
If $2K\equiv g_{ab}\dot{x}^a\dot{x}^b =\dot{x}^a\dot{x}_a $ then you can quickly read off $\Gamma^a _{bc}$ from the geodesic equation in the form
$\frac{\partial K}{\partial x^a } - \frac{d}{ds} (\frac{\partial K}{\partial \dot{x}^a})=0$ where $2K=\text{C}=0,+1,-1$.
Example:
$ds^2 = \eta^2 d\tau^2 - d\eta^2 \to K=\frac{1}{2}(\eta^2 \dot\tau^2 - \dot{\eta}^2 ) $
$\frac{\partial K}{\partial x^a } - \frac{d}{ds} (\frac{\partial K}{\partial \dot{x}^a})=0 \to \frac{\partial K}{\partial \tau } - \frac{d}{ds} (\frac{\partial K}{\partial \dot{\tau}})=0\to2\eta \dot{\eta}\dot{\tau}+\eta^2 \ddot{\tau}=0\to$
$\ddot{\tau}+\frac{2}{\eta} \dot{\eta} \dot{\tau}=0\implies\Gamma^\tau _{\eta \tau}=\frac{2}{\eta}=\Gamma^\tau _{\tau\eta}$
