How can I paint on a model to create embossed details?
In the video he is painting to a texture that is then used to control a Displace Modifier which changes the mesh. This method will work on any mesh provided you have a good even UV unwrap and enough face density on your mesh. You will also need to add a subdivision modifier above the displace on the modifier stack to make sure there is enough detail to displace. If your painted strokes do not match the topology of the mesh very well, you may get some jagged edges/artifacts, but these can be solved by retopologising at the end (which you should do anyway).

Towards the end of the video there are subtitles explaining a lot of what he is doing.