Many people told me doing gestures is great as a learning tool, gives you the pencil mileage, feeling for shape, form and proportion, and so on.
I started doing them, basing my tries on this, this and this video among others.
I've actually found doing gesture drawings fun and helpful - I'm seeing improvement! I began wondering - are there any similar, established exercises for drawing faces?
The links you provide are are illustrating exaggeration, not gesture drawing per se.
Gesture drawing "proper" is an attempt to get at the essence of a pose without falling to nitpicking details. It is a good exercise only insomuch as it trains you to develop a context and a framework for the further detail you will inevitably bring later on.
The problem with gesture drawing and especially the videos you link is that they are impressive to you as a learner, but exaggerating features immediately distorts the entire scene which you are mapping. When you go deeper and develop the drawing, all of the established relationships within the drawing will be inaccurate and you have no firm framework for measurement.
For artistic synthesis, this isn't a big problem, but your question itself implies that you are interested in accurate rendering.
If you apply the techniques displayed in those videos to faces, the thing most people are most familiar with, you will never get beyond caricature.
Zen Observation of the Day: in a drawing the difference between a finger pointing and the middle finger is about 1 mm and 4 degrees rotation.
I found it disconcerting that some here are claiming gesture is only useful for caricature and not professional, fine art or rendering. Nothing could be further from the truth.
You are learning figure drawing. Go to a college or institution, begin figure drawing classes. They will all begin with gesture. Gesture is about capturing the action, defining relationships to the various parts of the human figure and simplifying the figure to the simplest forms. Kind of like algebra: remember reducing fractions to their simplest terms? That is what gesture should be about. Economy of line, economy of time and, most of all, learning how to see the human figure as a whole.
We begin to learn how to figure draw with gesture. We do not concern ourselves with proportions, accuracy nor details. These are complex practices and would be disastrous to attempt to learn at the beginning. Would you begin driver's ed by teaching your student to drift? Or a first grader to begin math lessons with trig? No. Run from anyone who advises to begin learning figure drawing with anything BUT gesture.
If you do not begin to learn figure drawing with gesture, as you advance in skill, your work will always look stiff and awkward. Gesture teaches you about the dynamics of the figure, how it moves, how it flows. It teaches about the relationship of the parts of the figure to each other and how they express movement. Exagerate your gestures and push the dimensions on purpose. Attempt to find how far you can push your gestures until the figure 'breaks'. This is the barrier. Once you find it, pull back.
By starting figure drawing this way, your art will be dynamic, in motion. We use exaggeration because we are not copiers, we are artists. We are not attempting to duplicate what we see with 100% flat accuracy like a camera (God forbid). We are making statements. Your art should be a story of what you saw in the model, in the scene. Make it your own. If you wish to paint like Michaelangelo, Leonardo and the like, gesture is the first step. It will provide the foundation to build your fine art skills of mastering figure drawing upon.
Disregard the inexperienced who tell you otherwise. It may take 10,000 hours but in the end, being able to render like the great masters and beyond will be priceless. And gesture does not take you to caricature. That is the silliest thing I have ever heard.
I find that simply sitting down and drawing someone quickly, gesture style, adding more detail across the entire picture as I go helps. Whether you spend 2 minutes or 20 minutes on it, you should have the entire picture. I think this style of drawing is mostly a "seeing" exercise, which will help you with drawing in general.
To answer your question: In addition to these, blind contours are great too. They force you to see all details (even if they come out horrible). With time, you'll actually get recognizable images.
I agree with @horatio - caricature-ish is not the place to start. I disagree with @zach in spending 2-20 minutes and taking in the whole picture.
Where I come from, it is called Croquis. It is a technique where the aim is to "clock up the pencil hours". It is about learning to see more than anything. The point is to draw quickly, hardly looking at the paper, no corrections, or detailed fiddling. Use 10-20 seconds on each drawing, then start again. After you have done about 20-30 drawings stop, and look over what you have done.
If you during one drawing feel that you cannot really do much more to it, go to the next. Do not try to improve it there and then.
What happens is that the ones you thought were bad, might turn out to be the best ones. It is an extremely efficient way of learning to capture the essence.
Put these in a drawer, do not throw them away. When you have had a few more sessions you can look at them and see again, with new eyes.
This style of drawing is fast, intuitive and without censuring. Do not overthink, do not get bogged down in the structural "rules" of proportions. This will not help.
I used to do this while on public transport, as you have little time as people move around. It forces you to stop when people leave, and you can go over to the next drawing without getting bogged down in details.
Another good, more detailed exercise it drawing negative space. I will try to exemplify this idea here. When drawing an object, you have to imagine and decide where the borders between light - shadow goes. You are essentially taking 3D space down to 2d, and this is done by imagining negative space. A background has a shape, it is just the negative space of the object. Sometimes it is helpful to draw the background, rather than the object. Here is one image getting increasingly complex. But the last one is not always the best, just because it is the most detailed. It always depends on what you wish to accomplish.
If you would like to move on from the type of drawing you are doing just now to a more detailed image then try posemaniacs.com they have a huge range of 3D built images that show skeleton and muscles - it really helped me to understand the muscles and the different shapes that the body has. Also try this site http://artists.pixelovely.com/practice-tools/face-expression-practice/ for drawing faces.
Try the kind where you don't lift your pen (forget what it's called). It's really helpful for understanding the relationships between features and the 'Flow' of a face.
contour drawing, if you do not look at your own drawing while performing this trick, it is called blind contour drawing