Is there a distinction between rest mass and relativistic mass for photons? I'm trying to reconcile how photons do and don't have mass, and the distinction seems to come from the frame of reference. As far as I understand, if you were to somehow stop a photon relative to an observer so that it was at rest, you wouldn't be able to measure its mass, probably for multiple paradoxical reasons, although maybe in some weird scenario you could decohere perpendicular photons and measure the effects, but anyway, photons can't stop, so they can't have rest mass I guess.
However, how do we know which causes the other? Do they not have rest mass because they must stay in motion? Or must they stay in motion because they formed in such a way that they never could have had rest mass to begin with?
And then, how do they have mass simply by not being at rest?
 A: Photons don't have rest mass because if they did, then they would have an infinite amount of energy. For all particles with mass, it requires an infinite amount of energy to accelerate it to the speed of light. This can be seen from the formula for the energy of a particle, which is of the form $E={\gamma}\dot {mc^2}$. $\gamma$ approaches infinity as the velocity goes to c, which means that $E$ approaches infinity too. Therefore, we see that the property we call "rest mass" must have a value of 0 for all photons (at least if we define the quantity "rest mass" to be whatever the quantity $\frac{E}{\gamma c^2}$ approaches to as the velocity goes to c).
For a similar reason, we see that all particles with 0 rest mass must move at the speed of light, for if they didn't, then according to the formula above, they would also have 0 energy. But no physical particles can ever have 0 energy, so we see that they must move at the speed of light to be a physical particle in the first place. But I should note that nothing causes anything here. All we have done is conclude that for both statements "we have a physical particle" and "the particle has 0 rest mass" to hold, the particle must move at c. At least this is how I think about it. Perhaps someone else have different thoughts.
A: 
if you were to somehow stop a photon relative to an observer so that it was at rest

You cannot stop a photon. In special relativity, it's not even possible to consider a situation in which you could stop a photon. A reference frame in which a photon is at rest does not exist. There is no "if" about it; this is specifically forbidden by one of the most fundamental assumptions in special relativity, namely, that the speed of light is the same in all reference frames. There is no amount of kinetic energy that will get you to a frame where the photon is even slowed down, let alone stopped. A world in which this is even a possibility is one in which special relativity is wrong, and the assumptions of special relativity need to be replaced by something else which you have not specified (for example, Galilean invariance).

although maybe in some weird scenario you could decohere perpendicular photons and measure the effects

The "rest mass" of a system of multiple photons does indeed exist, as long as those photons aren't collinear; namely, it's equal to $\sqrt{E^2_{total}/c^4-|\vec{p}_{total}|^2/c^2}$. But this isn't the same thing as the rest mass of an individual photon; you can think of this as the rest mass of a massive particle that decayed to produce those two photons.

However, how do we know which causes the other?

The notion of "cause" in this context doesn't make a whole lot of sense. Physically, there is no causality at work here. We don't have one event that results in another event occurring at some later time. Instead, we have two properties ("object A travels at the speed of light" and "object A has zero rest mass") that always accompany each other; one is never present without the other. The two properties are basically equivalent by definition; if you assume one (doesn't matter which one), the other immediately follows.

Do they not have rest mass because they must stay in motion?

This statement isn't precise enough. It's not just that photons must stay in motion: rather, it's that photons must always be moving at the same speed. So, the following statement is true: if you assume that an object has no rest frame, (and you assume that the rest mass must be a real number), then special relativity dictates that the object has zero rest mass and also must always travel at the speed of light.

Or must they stay in motion because they formed in such a way that they never could have had rest mass to begin with?

See the last paragraph; the same statement about precision applies here. The following version of this statement is true: if you assume that an object has zero rest mass, then special relativity dictates that the object must always travel at the speed of light.

And then, how do they have mass simply by not being at rest?

I assume you're talking about "relativistic mass" here. It's much, much clearer to call it by its better name: total energy. Relativistic mass has been basically discarded as a concept, mostly because there's no intuitive benefit to labeling the total energy of an object as a "mass", and doing so creates far more confusion among people trying to learn relativity. The "relativistic mass" is literally just the total energy of an object. And, from that perspective, this question is trivial: an object has a nonzero total energy if it is moving.
A: To directly answer your question, a particle having zero rest mass implies that it must be moving with speed $c$, and objects which move at $c$ in one frame must do so in all frames.  On the other hand, if a particle is moving at speed $v=c$ then its energy must be equal to $pc$, which implies its mass is equal to zero.  In that sense, $m=0$ implies, and is implied by, $v=c$.  In the following, I'll try to explain this in more depth, and then mention the (largely unfashionable) concept of relativistic mass.

Here is my favorite interpretation of rest mass in special relativity. The general energy-momentum relationship for a particle is
$$E=\sqrt{p^2c^2 + m^2c^4}$$
If $m=0$, then $E = pc$, and the relationship between $E$ and $p$ becomes linear.  If $m\neq 0$, then the relationship is nonlinear, but becomes approximately linear for values of $p$ which are large compared to $mc$.

This is a plot of energy vs momentum for various values of $m$ (in natural units, $c=1$), with the non-relativistic $\frac{p^2}{2m}$ approximation superposed on top with dotted lines.  As you can see, the mass of the particle defines a particular momentum scale $p = mc$, below which the nonrelativistic approximation is good and above which the energy/momentum relationship is essentially linear.
The smaller the mass of the particle, the smaller the range of momenta for which the particle could be considered nonrelativistic; if the particle has zero mass, then it is relativistic for all values of its momentum, as is the case for the photon.

At the same time, one can express the velocity with which a particle moves as
$$\mathbf v = \frac{\mathbf p c^2}{E}= \frac{\mathbf pc^2}{\sqrt{p^2 c^2+m^2c^4}} = c \frac{\mathbf p}{\sqrt{p^2+m^2c^2}}$$
Here is a plot of the magnitude of $\mathbf v$ against the magnitude of $\mathbf p$, again for various masses.

Just as before, the mass defines a cutoff.  This time, for $p<mc$ we find that $v\approx p/m$, while for $p>mc$ we find that $v \approx c$.  The smaller $m$ is, the smaller the range of momenta for which $p=mv$ is a good approximation.  If the particle has zero mass, then $p=mv$ is invalid for all $p$, and we have simply that $v=c$.

The relativistic mass, on the other hand, arises as a desperate attempt to hold on to the expression $\mathbf p = m\mathbf v$.  Inverting the expression in the last section,
$$\mathbf p = \frac{E}{c^2}\mathbf v $$
The quantity $\frac{E}{c^2}$ is defined to be the relativistic mass $m_r$. Note that $\frac{E}{c^2} = \sqrt{\frac{p^2}{c^2} + m^2}$, so if $m\neq 0$ this can be written
$$\frac{E}{c^2} = m\sqrt{1+\left(\frac{pc}{m}\right)^2} \equiv \gamma m$$
and so in that case,
$$ \mathbf p = m_r \mathbf v = \gamma m \mathbf v$$

Over the past 100 years, the physics community has largely decided that the concept of relativistic mass is more trouble than it's worth.  It doesn't actually yield any useful insights - if anything, it obscures the fact that reality is fundamentally relativistic  - so it has fallen out of favor as a concept.
