Ho boy! Some time back I'd have already posted a wall of text, now I keep typing and deleting my thoughts... first thing I have become aware of - whatever lead they go with, there will be a group of fans not happy with it.
If I had to think of a entirely new lead, I'd go with a duo, a seasoned veteran and a young rookie, give each their own missions, but not make one character's set of missions reversal of the other character's (in other words, the infamous backtracking Dante did). This way you can satisfy the biggest amount of fans, both those that like manly older heroes and those who are into your standard shounen hero, while riding again on the very popular mentor-student dynamic.
Or you can make them both on about the same level of experience, maybe one higher in power than the other, with their personalities clashing while the situation forces them to cooperate. I was gonna say it kinda makes me imagine young, pre-DMC3 Vergil and Nero's hypothetical mom, but then I remembered how people think these days and DMC doesn't need shippers and anti-shippers outrage.