Ultimately when it comes to total nuclear war, you can expect ALL countries to be struck, especially when you have an ordnance count like what you describe. The reason the war starts is irrelevant. Having nuclear weapons makes you dangerous to others; using them makes you a threat. Any power launching their weapons is going to have to know that retaliation will come from somewhere, or at least that a pre-emptive strike from a neutral nuclear power is imminent as they've shown the willingness to use these weapons on their enemies; it's only a matter of time before we (the neutral party) is seen as an enemy.
From that perspective, everyone will go in one strike. The only thing that we really need to account for is the order, or the priority of different strikes. So, the breakdown will go something like this;
1) Enemy States
2) Neutral Nuclear States
3) Neutral Economically powerful States
4) Friends of All of the Above
Missile silos will be targeted first, then major cities. Perhaps very large infrastructure like dams or nuclear power stations. The rest you leave.
Why? Because you're trying to defeat your enemies (and potential enemies), not wipe them out completely. There's a good reason for that. You still need arable land to farm to feed your own survivors. If someone else retaliates and wipes out everything you can think of in your own land, whatever people survive are going to need to migrate, and take over lands of others. So you leave something for them to conquer, and generally make sure everyone domestically knows where that will be. By convention, everyone else will do something similar. This means that you've wiped out entire economies and technological capabilities and it could take generations for that to be reinstated, assuming the knowledge survives.
Ultimately such a war is going to make the earth a hard place to survive on for some time. Nuclear winter, major infrastructure and population centres gone, massive numbers of people dead and the survivors left with little to no leadership or governmental infrastructure. The order of destruction almost becomes inconsequential dealing with such a war.
So; the question becomes, where would you like to be in such a case?
The answer is Broome. Broome is a community in North-Western Australia. Australia has the geographic size of the USA, but all the major cities and are based in the South-Eastern part of the country. Even Perth and Darwin, the closest capital cities, are thousands of kilometres away. So; even if Australia gets hit, this town, close the equator, good fishing community, is largely free of radiation (depending on weather conditions), and can potentially start some agrarian practices (along with fishing) to survive. In a nuclear winter, it's possible (though unlikely) that its proximity to the equator may make it more livable than most of the major population centres on Earth that reside far closer to the poles (except for Asia and the Middle East of course).
Broome's risk of radiation contamination is ironically more likely to come from Jakarta (Indonesia's capital) than from an Australian target. Even in such a case, it's still remote enough to be relatively safe.
All in all, this is still a bad scenario and given that all targets are likely to retaliate according to the same priority list, pretty much every country will have inbound within minutes of this war breaking out.
Einstein once said that he didn't know with what weapons WW3 would be fought, but that he knew that WW4 would be fought with sticks and stones.
Even in this scenario, he'd be right.