You could have a PoD set after Constantine's death : for some years, Constantinople was relatively neglected by Roman elites, and it wasn't a systematical imperial residence. There were still imperial constructions going on, but it's really the disaster of Adrianople that allowed Constantinople to appear as the obvious imperial center in the region. Constantinople's strength came from Constantine's constant policy of promotion of his new capital : it was hard to ignore all the features making the cities a New Rome, without damaging one's legitimacy, and its Christian character really owed her a great aura in the IVth century.
But while a PoD before or during Constantine's reign would be definitely easier, a later PoD remains doable in any case of destructive event (such as a big fire, or a pagan reaction comparable to Julian's, etc.) until the late IVth.
As for Nicomedia...The city was important, but lacked Constantinople's legitimacy : remaining an imperial capital is doable, but it wouldn't benefice as much from supply capacities and be relatively open, especially after the IVth century earthquakes. I could see Nicomedia being an imperial capital, but not a really stable one, possibly a rotating capital of sorts with Thessalonica which I think would be eventually a better alternative with advantages close to Constantinople's. So maybe the maintain of late roman habit of itinerant imperial court for a longer while?
