Can we have a full-fledged PKI with just a strong signature scheme when factoring and all varieties of DH are broken?
Of course we can; we have a number of signature algorithms that do not rely on either factoring or DH (or Discrete Log, for that matter)
how long would such an effort take?
That's the hard question; while efforts are currently underway (because of the possibility of Quantum Computers, which would be able to solve all the problems you have listed), it's not expected to fully replace RSA or E*DSA[1] for perhaps 10-20 years (10 years would be when the large majority of PKI would be "postquantum"; 20 years would be the time it'd likely take to convince every obscure webserver to convert).
In your scenario, all this would need to be drastically sped up. The time that'd take would have to be an estimate; there are the problems that'd need to be solved (and I'll focus in on the PKI piece; there are other pieces, such as key exchange, uses of signatures disconnected from the global PKI, and more advanced crypto, such as IBE and PAKE, that would also need to be addressed).
We'd need to select a signature algorithm; such an effort is currently underway, however we're hoping to have two or three more years to gather information to allow us to make an informed choice; in your scenario, we can't wait that long. I'm guessing the community would pick one (likely either Falcon or Dilithium) in a month or two - those two are the most likely, because testing has shown that neither would slow down TLS significantly, and the best evidence we have now show them likely to be secure (and we're hoping to firm up that last statement in the next few years).
The various PKI vendors would need to issue new root public keys using this new method (and distribute them). How long this would take is more a question about internal company politics more than practicalities; some CA vendors will jump on the ball immediately; others (based on my conversations I've had with them over the years) are more likely to ignore the problem until forced to by customer demand.
Various browsers (and software libraries, such as OpenSSL) would need to incorporate these new methods and root public keys (and somehow deal with older websites that haven't updated yet). From my experience, all the major browser vendors are likely to be fairly quick about this. On the other hand, other clients (which might not be presented as browsers to the user) might be considerably slower to update.
Various websites would need to have new certificates issued to them, and to use the new signature method. That's a long pole - the major websites (Google, Amazon) and website hosting services (CloudFlare) are likely to be quick about this. On the other hand, there is a large number of smaller, not that well maintained servers that will be quite reluctant to upgrade (even if they are still being actively maintained).
Going through this list, my guess is that a significant amount of the web traffic would likely to be protected by an upgraded PKI in perhaps 6 months (of fairly intensive work by the community); however there will be some traffic that won't be for years...
[1]: E*DSA is my personal terminology for the collection ECDSA, EdDSA, Schnorr signatures and similar schemes.
