When does the first "random mutation" of DNA (have to) occur?
Random mutations happen everywhere in the body all the time. Most are harmless, some cause problems, some cause cancer. Some are beneficial. If a beneficial mutation occurs in the germ cell line, it will be passed on to the offspring. Depending on how beneficial it is, it can spread like wildfire (the mutation allowing lactase to continue to be expressed after infancy is a good example of this, as is sickle cell trait); if it is harmful, the carrier may die before birth, in infancy, etc. If it causes a later onset disease (e.g. early Parkinson's)1, the carrier has time to mate, reproduce and pass the disease on to their offspring. More and more diseases are being found to be genetic in nature now that genetic studies are so much easier to perform.

Again, for a mutation to be passed on, it must occur anywhere in the germ cell line of a parent, right up to the last stage before being released as an ova or a sperm cell, during fertilization, or during the very early stages of embryonic development in cells genetically programmed to become germ cells. If it occurs after fertilization, it will not affect that person, but its offspring. Depending on how early the mutation occurs, it may affect other parts of the reproductive system as well.

If a mutation happens in an embryo in a non-germ cell line, it may affect that person mildly, profoundly, not at all, or the embryo may die if it is a deleterious mutation in a critical organ system, say the heart.

But you need not put random mutations in scare quotes. I'm pretty sure you don't trust me, but they happen all the time, in every tissue, in you yourself as well as in everyone you know and everyone you don't know. And, by the grace of God, many of them can be repaired, and we don't ever have any ill effects from them. Alas, not all are repaired, and some lead to cancer.

Hereditary Early-Onset Parkinson's Disease Caused by Mutations in PINK1