Usually they still have some exposed solderable surface on the side. It is not ideal, but possible to use them. If your package does not have anything at all, which often happens with MEMS oscillators, then there are not too many options.
But yes, for better results you need hot air station. No need for a stencil or anything else. Just tin the pads using normal solder and then use hot air station to mount the part. For crystals it is usually pretty easy (compared to QFN and other stuff like this).
Noticed the link. You can clearly see that pad contacts extend to the corners. So the solderable castellations are right on the corners of the devices, not on the sides as in the video.
As for the footprint - you can probably find one, it is more or less standard 2.5x3.2mm package. But most small 4-pin footprints will work, especially for manual soldering.