"a new life" is 100% natural in some sentences, but sounds somewhat unnatural in this sentence, perhaps because the sentence as a whole is describing something specific/definite, rather than general/indefinite.
With your sentences, I would say:
(c) ◎
(d) ○
An example of a perfectly natural sentence with "a" is:
When he moves to Chicago, he can start a new life. ◎
However,
When he moves to Chicago, he can start his new life. × or △
sounds unnatural.
The differences in these cases might have to do with definite vs. indefinite objects (i.e., the same type of difference that affects whether "the" or "a" is used).