Have the game take place 2-3 years after the first one. The war between humans and demons is still going on, but humans are on the losing side. While there is still resistance and active fighting, a lot of humans have willingly accepted slavery over death. Some have even been helping the demons in exchange for power.
Dante is worn down and losing hope. He feels like he failed as the world's protector. And the world, once inspired by Dante, is now losing faith in him as well. Then Vergil shows up. He shows up like a knight in shining armor. He's going to lead people out of the darkness and demon control. All people have to do is trust him.
Dante, of course knows what is really going on. He tries to fight against Vergil, but that also means siding against other people. Mankind has now been divided into several different groups: those who side with Dante, those who side with Vergil, and those who side with the demons (willingly go otherwise). This of course creates a huge freaking mess.
That's what I want from DmC2 in terms of story. Not sure about gameplay yet. There are so many little things that could be improved. I'll have to think about this more.