Does randomness prevent collision attacks?

Yes, randomness that is controlled by the signer and that (crucially) is unpredictable by the attacker eliminates the potential for a collision to be generated, including the chosen-prefix style of collision attacks that were used by researcher to create a fake CA in 2008, and the authors of the Flame malware to create a fake signing certificate a few years later.

The reason is this: To create a collision attack, the attacker must have control over both inputs. That doesn't mean that both inputs are necessarily entirely arbitrary./ Indeed as you know, they certainly aren't, either for the forged certificates, or for the PDFs that Google created in their experiment. There is quite a lot of structure in fact. However, they attacker still needs to know exactly what the fixed components of the two inputs are, in order to be able to generate the components of both inputs that will ultimately allow the hashes of the full inputs to collide.

So, when the attacker does not control and cannot predict what the final form of one of the input is, he cannot create in advance the data that would need to be in the input he submits to the signer to sign. He only discovers afterwards the full input data (including the nonce) and the resulting hash. This fundamentally changes the problem from the need to create a collision, to the need to create a second pre-image, which as you've noted is a much, much harder problem, and something that is not even currently possible with MD5, if it ever will be.

So, I would say that yes, the introduction of unpredictable randomness does indeed eliminate the potential for collision attacks as a class.