Assuming you have such a unbeatable and invincible virus, there would never be a transition to a new World-Wide internet network.
Firstly, it becomes too risky to maintain the integrity of a new network. With billions of users world wide, all it takes is 1 idiot to connect an infected/old device and your new network is corrupted and you have to start again.
Secondly, the amount of infrastructure required would to be too much of an investment for any group or country to support. You would need to get new cables across the world, replace satellites, phone, radio towers, basically all your electronic devices with wi-fi, bluetooth or networking capabilities would need to be replaced and put away.
Thirdly, all the data would need to be copied over manually. There would be no way to get a device into the old network then the new network without transferring the virus over based on your description. People would need to manually retype everything they have. Billions of lines of code would need to be retyped, or printed out and scanned in with some super impressive OCR device (all built without ever connecting to the old network).
Now you haven't mentioned what exactly it is the virus does, so there are many ways it can branch out. If its making the devices physically unusable, then you will never recover the world-wide net as we know it. If the virus makes it hard to use the net but not impossible, its entirely possible to keep using the old virus infected network. Since it affects everything, the flaw applies to everything so who cares. Just keep going.
The most practical solution would be that companies that require a secure computer system will simply create their own and never connect them to the internet. Data will be copied between the two networks manually to ensure no infection. Normal people will continue to use the old network because there would be no company or country willing to sponsor such a tool and not have ownership of it, bringing up the entire, who owns the internet debate. (The time frame for this could be anywhere from 1 month to several years depending on who is doing it, the size and complexity and if they have any current projects underway. e.g. google and amazon would be able to pick up pretty quickly since they are constantly building new data centers and laying cables. Military and such would take longer since they have stricter requirements and will hire contractors. )
You really need to explain what it is that this virus does that makes the internet unusable. You're basically already being monitored and your ISP could effectively man in the middle you and steal all your data. You have government agencies monitoring all network traffic and most people would happily post their data on Facebook or other social media where companies can grab/buy it. There are already spyware and ransom ware software all over the internet and I believe there have already been some viruses that simply destroy your computer. You need to choose your poison because some of the things you want a virus to do are already being done and have no impact on people's use of the internet.