My idea is to use a material's Particle Info node and route the Index property into a noise texture to provide a brightness.
You'll notice I animated the Y coordinate of the texture so that the brightness of each particle changes over time. If you have immobile particles and want the animation to loop you could build nodes to set
z=cos(theta) where theta is a function of time to loop the coordinates over the course of the animation.
I rigged my animation to use an Object as the particle render instead of a halo, and the material is on the particle object. The emitter object's material seems to be irrelevant when using Objects to render particles.
My animation turned out EXTREMELY blinky. I suspect it would calm down if the slope on the fcurve of my Y texture coordinate were shallower.
Of course, the texture node you use (and what parameters you use to configure it) will affect the blinking behavior as well.
I used an emission node, but that means that my particles can be black. If you want them to be transparent, then use a white emission BSDF and a transparent BSDF, and route the output of the texture node into the factor of a mix node that mixes the emission with the transparent BSDF.