How can a generic potential transform under Lorentz transformations? The standard relativistic particle Lagrangian is
$$L = - \sum m_i \sqrt{1-v_i^2} - V(x_i).$$
The first term contributes a scalar to the action, as it should, but the second term is not clearly a Lorentz scalar; it contributes $\int V(x) \, dt$, so to make it Lorentz invariant we need to know how $V(x)$ transforms.
For example, in the case of electromagnetism, we have $V = q \phi$. The resolution to this problem is that the full coupling is actually $q (\phi - \mathbf{A} \cdot \mathbf{v})$. Then the potential contributes $\int A_\mu dx^\mu$ to the action, which is manifestly Lorentz invariant.
I'd like to know how this works for a general potential $V$, besides just the electric potential. (Examples might include $V = kx^2/2$ or $V = -Gm_1 m_2/r$.) Does it make sense in general to make $V$ part of a four-potential, or perhaps more general? If so, what do the other components physically represent? 
 A: If you assume $V(x)$ to be a scalar, then Lorentz invariance implies that
$$
V=V(x^2)
$$
where $x^2=t^2-\boldsymbol x^2$. For example, the relativistic harmonic oscillator has
$$
V=\frac12 k x^2
$$
One may also allow for $V$ to be velocity-dependent, in which case one may use the scalars $x^2,u^2,u\cdot x$ in the potential (though I don't know of any real-life system that uses this).
If you allow for $V$ to be something more general than a scalar, then you can have a more general dependence of $V$ on $x$, e.g. in the OP, where $V$ is the zeroeth component of a vector. 
A more general discussion can be found in the wikipedia entry Relativistic Lagrangian mechanics. For example, the general analysis of Lorentz invariance becomes much more transparent in the reparametrisaiton-invariant formulation, where the Lagrangian reads
$$
L=\frac12 m u(\tau)^2+V(x,u)
$$
with $u=\frac{\mathrm d}{\mathrm d\tau}x$. Classical electrodynamics has
$$
V(x,u)=q\ u\cdot A(x)
$$
A: Well, that's exactly the point. Even in Galilean physics, you can have plenty of nonscalar Lagrangians, and they are very useful.
The classical potentials that you have enumerated (gravitational and elastic) are exactly two examples of nonscalar potentials. They are physically explained by the presence of a source that is external to the system (Earth's gravity in the first case, spring in the second case). When you apply transformations to the system, you do not change the location.
Even in the electromagnetic case, if the field described by the potentials is sourced by charges that are not described in the system, the extra piece that you get is not Lorentz invariant, as the potential does not change, being external. The electromagnetic Lagrangian is truly Lorentz invariant if you have no external fields, and use the potential to describe the field sourced by the charges that you are describing.
A: $V$ fixed/background
Let's begin by not worrying about what's sourcing the potential. If the physics is well-described in a particular frame by a potential $V$, we may (following the OP) set that potential to be the time component of a 4-vector potential $A$, which will then give a Lorentz-invariant theory. I'm not sure how to interpret the space-like components of $A$, but it is worth pointing out that in the case of Newtonian gravity, $V=-GMm/r$, one obtains the theory of gravitoelectromagnetism. In other words, perhaps the best we can do to interpret the components is to make an analogy with electromagnetism (we'll see velocity-dependent deflection after making a boost).
Of course this procedure is not a unique way to build a Lorentz invariant theory from a Newtonian one. Let us work using $4$-forces rather than $4$-potentials. Then we can write a $4$-version of Newton's Second Law:
$$F^\mu(x,v)=m_0\frac{dv^\mu}{d\tau},$$
where $x$ is the position and $v$ is the $4$-velocity. Expanding about $v=0$ gives:
$$m_0 \frac{dv_\mu}{d\tau}=F^{(0)}_\mu(x)+F^{(1)}_{\mu\nu}(x)v^\nu+F^{(2)}_{\mu\nu\sigma}(x)v^\nu v^\sigma+\cdots\tag{1}$$
The condition that the $4$-force be orthogonal to the $4$-velocity sets $F^{(0)}_\mu$ equal to $0$, $F^{(1)}$ to something antisymmetric, etc. It's clear that we need to keep at least $F^{(1)}$, which gives E&M-type theories. But Lorentz-invariant extensions that put the nonrelativistic 3-force $F_i$ into $F^{(2)}_{itt}$ rather than into $F^{(1)}_{it}$ are, I think, also possible.
$V$ sourced by matter
If we care about the way $V$ is sourced, we enter the domain of field theory, which is more constrained than the previous case. Before, we could allow the $F^{(i)}$ to vary arbitrarily over spacetime because an arbitrary preset background was okay (since the nonrelativistic potential was taken as an arbitrary preset background). But we are supposed to build the Lagrangian density of a Lorentz-invariant field theory only from the fields and their derivatives. Under strong assumptions like locality/renormalizability/etc, I believe we obtain the theories in Bruce Greetham's answer, but let's try a slightly more general context.
Assume a vector current $j^\mu$ sources the potential (like E&M but unlike GR), and assume the theory is linear (so only the matter, and not the potential field itself, sources the potential). Then we have a field equation that looks like:
$$F^\mu[A]=j^\mu,$$
where $F$ is some linear operator. Taking the Fourier transform, inverting $F$, and using that we only have $A$ and $k$ available to us to build Lorentz-invariant quantities, gives (I think):
$$A^\mu=(R(k)\delta^\mu{}_\nu+S(k)k^\mu k_\nu)j^\nu,$$
where $R$ and $S$ are arbitrary functions of $k$. Plugging in $j^\nu=\delta^{(3)}(x)\delta^\nu{}_0$ and looking at the $A^0$ term may give constraints about the $V$'s that may arise from such a theory, but I couldn't quite figure this out. (For instance, we obviously need 3-rotation-invariance, but I'm not sure if any 3-rotation-invariant $V$ arises for the right choice of $R$ and $S$. Contrast this with the previous section, where even non-rotationally-symmetric $V$'s could be promoted to $A$'s).
A: Your question has no answer since there is no sensible classical relativistic multi-particle picture. A corresponding no-go theorem was proved by Currie, Jordan and Sudarshan, Reviews of Modern Physics 35 (1963), 350.
See also https://physics.stackexchange.com/a/32401/7924
