On-shellness of photons In principle, we could describe all physics without EM fields (or photons), as they are mainly a useful tool to describe "action at distance" (which does not mean instantaneous) between charged particle. In some sense, I could always integrate out photons, and describe only electrons and not have any changes in the observations (as detecting photons is done by observing how the motion of charged particles changes). With this picture, all photons are "virtual" (in the QFT sense), and we could expect them to always be off-shell.
My question is : why do we expect that photons that are "really emitted" (in a sense that should be made clearer, but that might mean "travelling very far before being absorbed") are always on-shell (i.e. having $E=p$)? Is it because the propagator of an off-shell photon decays very fast and therefore these photons can not interact with long distance charges ?
We could imagine that two very distant electrons (say, in two different galaxies) "scatter" each other (what we usually call "seeing a distant star")  with off-shell photons. Why is it not so ? Is it just because the probability of this event is very small ?
 A: A previous question has been signaled by Chris White, and I think that the answer of Arnold Neumaier is great. Now, let us add some hints relatively to your question.

In principle, we could describe all physics without EM fields (or
  photons), as they are mainly a useful tool to describe "action at
  distance" (which does not mean instantaneous) between charged
  particle. In some sense, I could always integrate out photons, and
  describe only electrons and not have any changes in the observations
  (as detecting photons is done by observing how the motion of charged
  particles changes). With this picture, all photons are "virtual" (in
  the QFT sense), and we could expect them to always be off-shell.

No, this is only true if there were only photonic internal lines, and only electrons external lines. So, in QED, we would practically restrict to tree diagrams. With loop diagrams , we would have to consider internal electrons lines ("virtual electrons"). So, your view should be "correct" only if you would consider a mixed of classical electron field and quantum photon field. But if you want to consider a unified theory of quantum fields (like QED), it is not correct. 

Is it because the propagator of an off-shell photon
  decays very fast and therefore these photons can not interact with
  long distance charges ?

You cannot mix momentum space and position space. Choose position space. If we look at the propagator $D(x)$, it is a function of $x^2 = \vec x^2-x_0^2$, $D(x)=D(x^2)$. So, the propagator, or the amplitude, does not decrease automatically because the spatial distance $|\vec x|$ is increasing. It depends on $x^2$. Of course, if $x_0=0$, the propagator is decreasing with $|\vec x|$ (in $\frac{1}{|\vec x|^2}$). This is true, also, that one may calculate the interaction energy between $2$ (fixed, eternal) electrons ($j^0_i(x) = \delta(\vec x- \vec x_i$)), for instance, and it turns that this interaction energy is in $\frac{1}{|\vec x|}$ (see Zee, Quantum field in a nutshell, Chapter I.4)

We could imagine that two very distant electrons (say, in two
  different galaxies) "scatter" each other (what we usually call "seeing
  a distant star") with off-shell photons. Why is it not so ?

But it is the case.
A: Our current mathematical models of everything depend on fields and interactions between them. These models have been verified for the microcosm, i.e. where the values of h_bar are, relative with the values of the variables, significant. In the quantum mechanical regime. 
Since our view of fields is such that everything can interact with everything as long as there exists a coupling constant and only the probabilities of interaction play a role, you could say that everything after the bing bang is virtual, off mass shell. 
In truth though it is the value of h_bar that defines what is measurable as probable or not. In the dimensions of the world we live in it has little meaning to postulate mathematical models where the events they predict with have a very small and unmeasurable probability, or very small and unmeasurable value, as in the measurement of mass. 
More so as we have in these limits the classical physics models which also work beautifully outside the microcosm dimensions. 
And in the end extending the mathematical models to unmeasurable unverifiable variable regions can tell us nothing new, it just adds complexity.
