How is REINFORCE used instead of Backpropagation? In neural networks with stochastic layers I've seen the use of the REINFORCE estimator for estimating the gradient (because it can't be computed directly).

Some such examples are Show, Attend and Tell, Recurrent models of visual attention and Multiple Object Recognition with Visual Attention.

However, I haven't figured out how this exactly works. How do we "bypass" the gradient's computation by using the REINFORCE learning rule? Does anyone have any insight on this?
REINFORCE is called a gradient estimator because it doesn't work on the true gradient, that comes from a loss function and the whole data, but makes up a heuristic loss, so that the gradient it ends up with isn't the true one. Let's see that with the REINFORCE equation:

$$
{\huge
\Delta \mathbf{\theta}_t = \alpha \nabla_{\mathbf{\theta}} \log \pi_{\mathbf{\theta}} (a_t \mid s_t) v_t
}%
$$

As this shows, the gradient is still there ($\nabla_\theta$). But the policy corresponds to the network's output, so we can use backpropagation to compute the gradient of that heuristic loss with respect to the weights. The real gradient is unknown to us, but this estimation will do the job.