Why experience replay requires off-policy algorithm? In the paper introducing DQN "Playing Atari with Deep Reinforcement Learning", it mentioned:

Note that when learning by experience replay, it is necessary to learn off-policy
  (because our current parameters are different to those used to generate the sample), which motivates
  the choice of Q-learning.

I didn't quite understand what it means. What if we use SARSA and remember the action a' for the action we are to take in s' in our memory, and then sample batches from it and update Q like we did in DQN? And, can actor-critic methods (A3C, for specific) use experience replay? If not, why?
 A: The on-policy methods, like SARSA, expects that the actions in every state are chosen based on the current policy of the agent, that usually tends to exploit rewards.
Doing so, the policy gets better when we update our policy based on the last rewards. Here in particular, they update the parameters of the NN that predicts the value of a certain state/action).
But, if we update our policy based on stored transitions, like in experience replay, we are actually evaluating actions from a policy that is no longer the current one, since it evolved in time, thus making it no longer on-policy.
The Q values are evaluated based on the future rewards that you will get from a state following the current agent policy.
However, that is no longer true since you are now following a different policy. So they use a common off-policy method that explores based on an epsilon-greedy approach. 
A: David Silver addresses this in this video lecture at 46:10
http://videolectures.net/rldm2015_silver_reinforcement_learning/:
Experience replay chooses $a$ from $s$ using the policy prevailing at the time, and this is one of its advantages - it allows the Q function to learn from previous policies, which breaks up the correlation of recent states and policies and prevents the network from getting "locked in" to a certain behaviour mode.
A: TL;DR: It isn't necessary to have an off-policy method when using experience replay, but it makes your life a lot easier.

When following a given policy $\pi$, an on-policy method (for value function estimation) estimates $V^\pi$ or $Q^\pi$ (respectively), whereas an off-policy method estimates $V^*$ or $Q^*$.
The off-policy case is desirable because it guarantees that the estimate of $V^*$ or $Q^*$ will keep getting more accurate even if the policy being followed changes, i.e., following $\pi_1$ will yield $V^*$, following $\pi_2$ will yield $V^*$ and randomly choosing between $\pi_1$ and $\pi_2$ for each step will still yield $V^*$. (If all state-action pairs are seen often enough, ofc.)
In the on-policy case, however, following $\pi_1$ will yield $V^{\pi_1}$, following $\pi_2$ will yield $V^{\pi_2}$ and randomly choosing between the two policies at each step will yield something that is not immediately obvious - at least to me.

In experience replay, the replay buffer is an amalgamation of experiences gathered by the agent following different policies $\pi_1, \dots, \pi_n$ at different times from which a random subset is drawn and used to improve the function approximation in a batch RL / supervised learning style.
Off-policy methods won't have a problem with this; they will happily take the samples and improve the estimate of $V^*$.
However, as we can see from the above, this scenario is very much not ideal for on-policy methods. The policy represented by $V$ or $Q$ will be a (random) combination of the policies in the replay buffer, and who knows if that policy is at least as good as the previous policy. If it isn't we can't guarantee an improvement once we act $\epsilon$-greedy on it.
Saving and using the $(s_t, a_t, r_{t+1})$-sequence, as you suggest, is being done by algorithms like A3C or PPO. You actually have to do this for on-policy methods, because they won't converge to $V^\pi$ or $Q^\pi$ otherwise. The problem here isn't if on-policy methods will converge when using experience replay, but rather what it is that they converge to, and if that what is still an improvement over the previous iteration.
One way of addressing this problem is to stick to off-policy methods; another is to use on-policy methods, a rolling replay buffer (to "keep the experience fresh"), and carefully tuning parameters (making very small steps). Essentially, we aim to make sure that the $V^\pi$ or $Q^\pi$ we actually learn is close enough to $V^{\pi_n}$ or $Q^{\pi_n}$ (from the latest iteration's $\pi_n$) so that we can guarantee an improvement when acting greedily wrt. $V^\pi$ or $Q^\pi$.
A: One answer is that by definition if you're using past experiences that were obtained using an outdated policy, then your method is off policy.
The question of why using experience replay is 'wrong' if you're using vanilla policy gradient i.e REINFORCE still remains though.
The critical point is that Q-learning methods depend on an expectation that is independent of the policy itself i.e. it does not matter exactly how you found out what is the expected return of a particular series of actions, whether it was by accident or through exploration or by following a policy, it's useful and stable data (see notes for equations 2 and 3 in https://arxiv.org/abs/1509.02971). In contrast, the expectation of the gradient in REINFORCE is dependent on the policy, so if you use the datapoints from an outdated policy to calculate the gradient of the parameters, it simply does not represent the expectation of the gradients of the updated policy anymore e.g. if the optimal theta_1 is 0.5 and then initially it's set to 0.0 and your sampled gradient tells you to increase it by 0.5, you will make the policy actually worse if you increase it yet again by 0.5 to have it equal to 1.
Where this difference shows itself though, is that with experience replay you cannot learn stochastic decision making. It's a trade-off between using fewer data points for converging to a possibly worse determinstic policy (a determinstic policy is a subset of a stochastic policy) against using more datapoints for obtaining a stochastic policy.
