Hamiltonian systems without a corresponding Lagrangian system I was playing around with a Hamiltonian model for the propagation of photons:
$$ H = c \sqrt{p \cdot p} + V(q) \tag{1}$$
which gives a meaningful set of equations of motion,
$$ \dot{q}_i = c \frac{p_i}{\sqrt{p \cdot p}} \quad \quad \dot{p}_i = - \frac{\partial V(q)}{\partial q_i}. \tag{2}$$
Notice that $$\dot{q} \cdot \dot{q} = c^2\tag{3}$$ always which is why I considered this as modeling the propagation of a massless particle.
However, this Hamiltonian has the following strange feature. If we perform a Legendre transformation to find an associated Lagrangian,
$$ \mathcal{L} = p \cdot \dot{q} - H = c \frac{p \cdot p}{\sqrt{p \cdot p}} - \left( c \sqrt{p \cdot p} + V(q) \right) = - V(q) \tag{4}$$
which is not dynamical since $\frac{\partial \mathcal{L}}{\partial \dot{q}} = 0$.
A similar problem arises if I consider a dual Lagrangian system in $q, \dot{q}$ variables and attempt to find a Hamiltonian by Legendre transformation:
$$ \mathcal{L} = c \sqrt{\dot{q} \cdot \dot{q}} - V(q) \tag{5}$$
then we get well-defined Euler-Lagrange equations:
$$ \frac{\mathrm{d}}{\mathrm{d} t} \left( c \frac{\dot{q}_i}{\sqrt{\dot{q}_i \cdot \dot{q}_i}} \right) = - \frac{\partial V(q)}{\partial q_i}\tag{6} $$
which becomes:
$$ (\dot{q} \cdot \dot{q}) \ddot{q}_i - (\dot{q} \cdot \ddot{q}) \dot{q}_i + (\dot{q} \cdot \dot{q})^{3/2} \frac{\partial V(q)}{\partial q_i} = 0.\tag{7} $$
However, if we try to find an associated Hamiltonian,
$$ H = p \cdot \dot{q} - \mathcal{L} = c \frac{\dot{q} \cdot \dot{q}}{\sqrt{\dot{q} \cdot \dot{q}}} - \left( c \sqrt{\dot{q} \cdot \dot{q}} - V(q) \right) = V(q) \tag{8}$$
which is again non-dynamical.
What is going on here? Is there an interesting reason that these systems should not admit Lagrangian/Hamiltonian descriptions? In general, when should I expect the Legendre transformation to give me a well-behaved system that reproduces the physics I started with?
 A: *

*The Lagrangian can be constructed directly by performing a Dirac-Bergmann constraint analysis of OP's Hamiltonian (1). In eq. (3) OP has already correctly identified the primary constraint$^1$
$$\dot{x}^2~:=~g_{\mu\nu}(x)~ \dot{x}^{\mu}\dot{x}^{\nu}~\approx ~0, \qquad \dot{x}^{\mu}~:=~\frac{dx^{\mu}}{d\tau}, \tag{A}$$
where $\tau$ is the world-line (WL) parameter (which does not have to be the proper time).


*The Lagrangian becomes the massless limit of$^2$
$$ L~=~\lambda \dot{x}^2-\frac{m^2}{4\lambda} - V,\tag{B} $$
where $\lambda(\tau)$ is a Lagrange multiplier, cf. e.g. this Phys.SE post.


*The momentum for the Lagrangian is
$$ p_{\mu}~:=~\frac{\partial L}{\partial \dot{x}^{\mu}}~=~2\lambda g_{\mu\nu}(x)~\dot{x}^{\nu}, \tag{C}$$
so that the corresponding Hamiltonian is
$$ H~=~\frac{p^2+m^2}{4\lambda} + V. \tag{D}$$


*Therefore the Hamiltonian Lagrangian becomes
$$ L_H~:=~ p_{\mu} \dot{x}^{\mu} - H. \tag{E} $$


*Let us now go to the static gauge $x^0=\tau$. If we integrate out $p^0$ and $\lambda$, we get$^3$
$$\begin{align} \left. L_H\right|_{x^0=\tau}
\quad\stackrel{p^0}{\longrightarrow}&\quad
{\bf p}\cdot \dot{\bf x}- \underbrace{\left(\lambda + \frac{{\bf p}^2+m^2}{4\lambda} + V\right)}_{\text{Hamiltonian}}\cr\cr
\quad\stackrel{\lambda}{\longrightarrow}&\quad
{\bf p}\cdot \dot{\bf x}  - \underbrace{\left(\sqrt{{\bf p}^2+m^2}+V\right)}_{\text{Hamiltonian}} .\end{align}\tag{F} $$


*If we put the mass $m\to 0$ then the square-root Hamiltonian (F) becomes precisely OP's Hamiltonian (1). This confirms our claim that the massless limit of eq. (B) is OP's sought-for Lagrangian.
--
$^1$ Let us work in units where the speed of light $c=1$ and with Minkowski sign convention $(-,+,+,+)$.
$^2$ The massterm in eq. (B) is included for generality and is not essential. The only slightly strange thing is that we restrict the $\lambda$ target-space from $\mathbb{R}$ to $\mathbb{R}_+$. This latter point is also discussed in my Phys.SE answer here.
$^3$ A similar argument was given in eq. (3) of my Phys.SE answer here, where the Lagrange multiplier $\lambda=\frac{1}{2e}$ is replaced by an einbein field $e$.
