NB This advice assumes your goal is to recognise expression in pictures of any person, and not just people from your training data.
Should the validation set consists of unseen subjects as well?
Yes. This will give you the most accurate measure of performance in the task you want to use the network in, in order to choose the best generalisation and take it forward to testing.
You would only use a simple random split if the end goal of your trained network is to recognise expressions from images of the people in the training set.
Or can I shuffle the whole training set and use a part of it (10-20%) as validation set?
No. If you take random samples where the same face appears in training and cv, you will get an over-estimate of generalisation. I have seen this effect first hand in the Kaggle State Farm Distracted Driver contest, and you should see it discussed in the forums there. It might be helpful for ideas to improve performance too.
if I use 10-20% of the training set as my validation set, my model learns with reasonable accuracy (45-50%) using a 3-layer CNN
This is a data leak between train and cross validation - the network has learnt to correctly classify expressions in images of people it has already seen, and that is what you are measuring by taking a split in this way. It is not surprising that the test result does not match the promising values from cross validation.
I'm just wondering which is correct since using a validation set of unseen subjects, my model starts to overfit after 3-5 epochs and doesn't learn at all
You are over-fitting regardless of how you split train,CV. When you split the CV incorrectly, then in addition to over-fitting, the data leak gives you bad guidance.
It looks like that you have very little diversity in the training data, whilst training an image classifier from scratch requires a lot of data. Consider:
Collecting more labelled data, perhaps some other dataset you can download.
Adding a lot of regularisation to your model (e.g. multiple dropout layers)
Using a pre-trained image classifier network (e.g. VGG-19 or Inception) as a starting point and fine-tuning it for your classification task.
Use full k-fold cross-validation regardless of the computational cost, to mitigate problems of using small training set. This won't help solve your training problems directly, but will give you a better shot at tuning your network hyper-parameters once you solve that issue.