I'm answering my own question to share some knowledge.
First, cold toes/fingers is serious. You start feeling discomfort, then a little pain, then you stop feeling them and forget about them, then you get them amputated. So you should constantly check if you can still feel toes and fingers, and if not, start to warm them up.
Second, I find most effective and easy the following method of heating:
- To warm up toes, swing your leg back-and-forward 30-50 times. The movement is done with the whole leg (including the thigh), as wide as possible, and it should be powerful.
- To warm up your fingers, make similar motion with your arms, except that you can go 360-degree.
Remember to make your full 30-50 swings before saying "blah, it's not working";)
What happens is you warm blood is driven by centripetal force to flow to the extreme parts of your legs/arms: toes and fingers. Normally they don't get much blood in cold conditions, because your body regulation mechanisms try to keep more warmth at the center of the body by thinning peripherial vessels (it's an overreaction).
If you weren't feeling your fingers/toes before starting this, warming up might be very painful. So it's better to do 20, small pause to let heat reach frozen tissues, a little screaming, another 20;)
Note: if you weren't feeling your toes or fingers for a long time, things may have gone beyond simple treatment. I'm not sure this method is advised in such situation, because it provides fast heating, and all recommendations for treating serious frostbites prescribe slow heating (also see this question about frostbites).