Motivation for Potentials This is a hypothetical question about "pedagogy".  Let's say I am trying to take someone who has just a very small amount of knowledge about Newtonian mechanics and convince them that the Lagrangian formulation of mechanics is a natural thing to try.  First of all, to convince them that this is natural, at the very least, I would have to show how one can reproduce Newtonian Mechanics from Lagrangian Mechanics, in particular, Newton's Second Law.  However, to do this, I would need to introduce the notion of a potential.  However, I am having trouble justifying this.
I would like to be able to say "most forces we encounter in nature are conservative, and hence, we are not losing too much by assuming all of our forces are conservative . . .".  However, of the two fundamental forces that come to mind in elementary physics, the gravitational force and the electromagnetic force, only one is conservative.  I hardly feel that one out of two is a sufficient justification for the introduction of a potential.  But if it is not even natural to assume that our forces always come from a potential, then it certainly won't be natural to define the Lagrangian in a way that reproduces Newton's second law.
Is there a nice way of convincing such a student that, even though the electromagnetic force is not conservative, there are still ways of deriving it from some sort of potential?  In particular, the difficulty here is that I do not want to assume they have any specific knowledge of electrodynamics.
 A: OP wrote (v1):

I hardly feel that one out of two is a sufficient justification for the introduction of a potential.

I) Here we would like to point out that there exists a velocity-dependent generalized potential  
$$U~=~q(\phi -  {\bf v}\cdot {\bf A}) $$
for the Lorentz force
$$ {\bf F}~=~ q({\bf E} + {\bf v}\times {\bf B})  . $$ 
Here $\phi$ is the scalar EM potential and ${\bf A}$ is the magnetic vector potential. The generalized potential $U$ is related to the force ${\bf F}$ as 
$$ {\bf F}~=~\frac{d}{dt} \frac{\partial U}{\partial {\bf v}} - \frac{\partial U}{\partial {\bf r}}, $$
see e.g., Herbert Goldstein, Classical Mechanics, Chapter 1, for details. So the electromagnetic force ${\bf F}$ has a potential in the sense of $U$. The Lagrangian is $L=T-U$.
II) Other examples are fictitious forces (centrifugal, Coriolis, etc.), where there also exist generalized potentials, see e.g., Landau and Lifshitz, Vol.1: Mechanics, $\S$39.
A: While the electromagnetic force is not conservative in the strict mathematical sense (that is, it cannot be written as the gradient of a scalar), it is conservative in the sense that it conserves energy. This is more than enough to motivate a quantity for potential, as you need some value to cover the non-kinetic energy. After all, the electromagnetic field can be expressed in terms of potential, it's just that you need a 4-vector as opposed to a scalar.
A: In gravitation and in electromagnetism, the introduction of potentials greatly enhances our problem solving power because it is usually much easier to sum the potentials due to sources and apply relationships between the relevant fields and potentials, than it is to try and find the vector sums of the fields they produce. In gravitation this is quite obvious - just use any >1 body problem as an example. Personally, I never mention the fact that the gravitational force is conservative as a motivation for using potential.
In electromagnetism maybe it is not so obvious, but the replacement of the E- and B-fields (two vector fields) with one scalar and one vector field is a simplification, especially when one can demonstrate that these two potentials are not independent but are related by a gauge. It allows electromagnetism to be encapsulated into a pair of symmetric inhomogeneous wave equations, rather than 2 vector and 2 scalar Maxwell's equations. Finally, it is the potentials that most naturally bind electromagnetism to relativity and quantum mechanics, though I would not use this as an initial motivation; more as a thing to be discovered later on.
