Are the rest masses of fundamental particles certainly constants?

I guess I can think of three possible ways in which masses could be non-constant. (1) They could change due to quantum-mechanical fluctuations, (2) they could be slightly different for different particles at the same time, (3) or they could change over cosmological time intervals.

Number 1 seems to be what you had in mind, but I don't think it works. The standard picture is that for a particle of mass m, its momentum p and mass-energy E can fluctuate, but the fluctuations are always such that $m=\sqrt{E^2-p^2}$ (with c=1) stays the same.

Re #2, here's some good info: Are all electrons identical?

Re #3, one thing to watch out for is that it is impossible, even in principle, to tell whether a unitful fundamental constant is changing. The notion only makes sense when you talk about unitless constants: Duff, http://arxiv.org/abs/hep-th/0208093 However, it certainly does make sense to talk about changes in the unitless ratios of fundamental constants, such as the ratio of two masses or the fine structure constant.

There are claims by Webb et al. J.K. Webb et al., http://arxiv.org/abs/astro-ph/0012539v3 that the fine structure constant has changed over cosmological timescales. Chand et al., Astron. Astrophys. 417: 853, failed to reproduce the result, and IMO it's bogus. I'm not aware of any similar tests for the ratios of masses of fundamental particles. If you change the ratio of masses of the electron and proton, it will change the spectrum of hydrogen, but at least to first order, the change would just be a rescaling of energies, which would be indistinguishable from a tiny change in the Doppler shift.

Brans-Dicke gravity (Physical Review 124 (1961) 925, http://loyno.edu/~brans/ST-history/ ) has a scalar field that can be interpreted as either a local variation in inertia or a local variation in the gravitational constant G. This could in some sense be interpreted as meaning that, e.g., electrons at different locations in spacetime had different masses, but all particles would be affected in the same way, so there would be no effect on ratios of masses -- hence the ambiguity between interpreting it as a variation in inertia or a variation in G. B-D gravity has a unitless constant $\omega$, and the limit $\omega\rightarrow\infty$ corresponds to general relativity. Solar system tests constrain $\omega$ to be at least 40,000, so B-D gravity is basically dead these days.

They most certainly are not. You are right that there is no theory that explains masses (these are input as parameters) but note that our current theories used to explain e.g. LHC data (that is, quantum field theories) inevitably come with a scale attached: you need to describe upto what energies you do physics otherwise the theory just doesn't make sense [insert usual story here about renormalization and infinities often told to scare little children before their going to bed].

Now, this shouldn't come as such a surprise since there are new particles awaiting discovery just behind the corner, so claiming that we have a complete theory would be preposterous. Instead, what we claim is that we have a good theory that works upto some scale. Consequently, all of the parameters that are inserted by hand must depend on the scale. Again, this is because theories at different scales are potentially completely different (e.g. at the "present scale" there is no supersymmetry assumed while it is conceivable that at a little higher scale our theories will have to include it) and so the parameters of the theories that are used to connect the theory with experiment potentially have no relation to each other. This phenomenon is known as running of coupling constants or, briefly, the running coupling.

The moral is that all the rest masses and interaction "constants" depend on some scale. They shouldn't be thought as something inherently deep about the nature but just as fitting parameters that describe only effective masses and effective coupling. To illustrate why they are just effective: consider an electron in classical physics. We can measure its charge by usual methods. This value is the long-distance low-energy $e(E \to 0)$ limit of the scale dependent coupling $e(E)$. As you increase the energy and try to probe electron at shorter distances you will find that lots of others electron-positron pairs appear, screening the electron, and the charge that you will measure will be different due to these changed conditions (we talk about the polarization of vacuum).

Just for the sake of completeness: one could say that $E \to 0$ limit is the most important thing about couplings and that we should take that as definition. If so, then these long-distance couplings are indeed constants as one was used in classical physics. But this point of view is worthless in particle physics where people instead try to make $E$ as high as possible to obtain a theory valid at high scales (since this is what they need at LHC).