Early stopping on validation loss or on accuracy?
TLDR; Monitor the loss rather than the accuracy

I will answer my own question since I think that the answers received missed the point and someone might have the same problem one day.

First, let me quickly clarify that using early stopping is perfectly normal when training neural networks (see the relevant sections in Goodfellow et al's Deep Learning book, most DL papers, and the documentation for keras' EarlyStopping callback).

Now, regarding the quantity to monitor: prefer the loss to the accuracy. Why? 
The loss quantify how certain the model is about a prediction (basically having a value close to 1 in the right class and close to 0 in the other classes). The accuracy merely account for the number of correct predictions. Similarly, any metrics using hard predictions rather than probabilities have the same problem.

Obviously, whatever metrics you end up choosing, it has to be calculated on a validation set and not a training set (otherwise, you are completely missing the point of using EarlyStopping in the first place)