Why can't any term which is added to the Lagrangian be written as a total derivative (or divergence)? All right, I know there must be an elementary proof of this, but I am not sure why I never came across it before. 
Adding a total time derivative to the Lagrangian (or a 4D divergence of some 4 vector in field theory) does not change the dynamics because the variation can be assumed to be zero on the boundary and integrated away.
But I don't see why any arbitrary function (as long as it is well behaved, no discontinuities, etc.) can't be written as a total derivative (or 4D divergence). In fact, I know that any nice scalar function in 3D can be written as a 3D divergence of some vector field, since for any 3D charge distribution, there exists an electric field whose divergence is equal to the charge function because of Gauss' Law.
But if I can write any function as a total derivative (or divergence of some vector) than I can add any function to the lagrangian and get the same dynamics, which means the lagrangian is completely arbitrary, which makes no sense at all. 
So my question is, why can't an arbitrary function (as long as it is well behaved, no discontinuities, etc.) be written as a total derivative of some other function (or divergence of a vector)?
 A: Let us for simplicity consider just classical point mechanics (i.e. a $0+1$ dimensional world volume) with only one variable $q(t)$. (The generalization to classical field theory on an $n+1$ dimensional world volume with several fields is straightforward.)
Let us reformulate the title(v1) as follows:

Why can't the Lagrangian $L$ always be written as a total derivative $\frac{dF}{dt}$?

In short, it is because: 


*

*In physics, the action functional $S[q]$ should be local, i.e. of the form 
$S[q]=\int dt~L$, where the $L$ is a function of the form
$$L~=~L(q(t), \dot{q}(t), \ddot{q}(t), \ldots, \frac{d^Nq(t)}{dt^N};t),$$
and where $N\in\mathbb{N}_{0}$ is some finite order. (In most physics applications $N=1$, but this is not important in what follows. Note that
the Euler-Lagrange equations get modified with higher-order terms if $N>1$.) 

*Similarly, we demand that $F$ is of local form 
$$F~=~F(q(t), \dot{q}(t), \ddot{q}(t), \ldots, \frac{d^{N-1}q(t)}{dt^{N-1}};t),$$
We stress that $L$ and $F$ only refer to the same time instant $t$. In other words, if $t$ is now, then $L$ and $F$ does not depend on the past nor the future.

*The special intermediate role played by the $q$ variable in between $L$ and $t$. Note that there can be both implicit and explicit time-dependence of $L$ and $F$.
Counterexample: Consider
$$L~=~-\frac{k}{2}q(t)^2.$$ 
Then we can write $L=\frac{dF}{dt}$ as a total time derivative by defining 
$$F=-\frac{k}{2}\int_0^t dt'~q(t')^2. $$
($F$ is unique up to a functional K[q] that doesn't depend on $t$.) But $F$ is not on local form as it also depends on the past $t'<t$.
Finally, let us mention that one can prove (still under assumption of locality in above sense plus assuming that the configuration space is contractible, due to an algebraic Poincare lemma of the so-called bi-variational complex, see e.g. Ref. 1) that 
$$ \text{The Lagrangian density is a total divergence} $$  $$\Updownarrow$$ 
$$\text{The Euler-Lagrange equations are identically satisfied}. $$
References:


*

*G. Barnich, F. Brandt and  M. Henneaux, Local BRST cohomology in gauge theories, Phys. Rep. 338 (2000) 439, arXiv:hep-th/0002245.  

A: Lagrangian is a functional of time, generalized coordinates, and time derivative of generalized coordinates. Obviously many scalars are not total time derivatives; $q^2$ for example.
As for Lagrangian density, keep in mind that it is the functional of field variables $\phi_i(x^\mu)$ and their derivatives $\partial_\mu \phi_i(x^\mu)$. It is not a composite function of coordinates $\boldsymbol{x^\mu}$. So the arbitrary scalar function, in the form of a divergence, indeed does not matter, because the function is of the coordinates, which is independent from the field variables.

Proof that $q^2$ cannot be rewritten as total time derivative: 
The total time derivative of any function 
$$F(q,\dot q,t)=\frac{\mathrm{d}}{\mathrm{d}t}f(q,t)=\frac{\partial f}{\partial q}\dot{q}+\frac{\partial f}{\partial t},$$
automatically satisfies Euler-Lagrangian equation (easy to prove by substitution)
$$\frac{\partial F}{\partial q}-\frac{\mathrm{d}}{\mathrm{d}t}\frac{\partial F}{\partial \dot{q}}=0.$$
$q^2$ does not satisfy the above condition, so it can't be written as total time derivative.
A: The reason for this is pretty simple. Let me consider the simple case of one dimensional motion (the generalization being trivial). The Lagrangian is a function of the generalized coordinates and (possibly) time $L=L(q,\dot{q},t)$. The equations of motion are obtained by making the action $S$ extremal
$\delta S[q]=0$,
where $S[q]=\int_{t_{1}}^{t_2} L(q,\dot{q},t) dt$.
Now let's add to the Lagrangian any arbitrary function $G=G(q,t)$ such that 
$G(q,t)=\dfrac{dF(q,t)}{dt}$. 
If the function $G(q,t)$ is Riemann-integrable [bounded and continuous except in a set of measure zero] then you can always find such $F(q,t)$. This is case of most of the functions which are interesting for physicists. Hence
$L'(q,\dot{q},t)=L(q,\dot{q},t)+G(q,t)$,
$S'[q]=S[q] + \int_{t_1}^{t_2}G(q,t) = S[q] +F(q(t_2),t_2)-F(q(t_1),t_1)$,
since when making a variation we impose that $q(t_1)$ and $q(t_2)$ are fixed. So we find that we have added a constant term to the Lagrangian and therefore
$\delta S'[q]=\delta S[q]$,
so the equations of motion are left invariant.
You say:

"...which means the lagrangian is completely arbitrary, which makes no sense at all..."

Indeed, the Lagrangian function is "arbitrary" in the sense that, respecting certain symmetries, it has to give you the correct equations of the motion when the action functional is extremal.
A: I started trying to answer this then found a web site that did a better job than I could, so here it is: http://en.wikibooks.org/wiki/Classical_Mechanics/Lagrange_Theory#Is_the_Lagrangian_unique.3F
This is really a comment, but it got a bit involved to go in a comment box:
Start with the Langrangian for a free particle $L_{Free}$ and add to it a function $G$ defined by:
$$G = L_{SHO} - L_{Free}$$
where $L_{SHO}$ is the Lagrangian for a simple harmonic oscillator. Can $G$ be written as a total time differential. If it can, the action for a free particle isn't changed by adding $G$ to the Lagrangian, and we have to conclude that the action for a free particle is the same as the action for a simple harmonic oscillator. Since this isn't the case that suggests $G$ cannot be written as a total time differential.
The function $G$ is obviously just $-kx^2$. I did try finding a function $F(x, t)$ such that the total time derivative was $-kx^2$ but without any luck, which doesn't necessarily prove anything.
A: A function that has only $x$ terms cannot be a  total time derivative because,
$${dF(x,\dot x,t) \over dt} = \dot x {∂F \over ∂x} +{∂F \over ∂\dot x} \ddot x + {∂F \over ∂t} $$
Here, you can't eliminate the $\dot x$ as long as you choose a $F$ that has only $x$ and no $\dot x$. Because if $F$ the has $x$ then, ${dF\over dt}$ must have $\dot x$. 
If you try to eliminate the term by including a $\dot x$ into $F$ you will now have to deal with the $\ddot x$ term now.
Similarly as you keep going you'll always have the highest order time derivative sitting at the end of the equation, that you just can't eliminate without including its higher order time derivative.
Since we generally don't see any physical systems that are dependent on time derivatives of order greater than $2$, we can stop here itself. This is just one of the many functions that I believe cannot be written as total derivative of time. 
