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} $$ A similar argument was given in eq. (3) of my Phys.SE answer here.
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 the correctOP'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$.