What you basically want is the alpha to be a probability that a pixel is opaque. I would do it like this:
float random = tex2D(g_dissolvemap_sampler, a_texcoord0).r; if(alpha < random) discard;
You can also use alpha-to-coverage, which will basically accomplish the same thing using a tiled screen-space dither pattern instead of a pure random pattern. You can also encode a set of dither patterns directly into a texture, and then lookup into that texture based on screen position and alpha value.