I downloaded GIMP solely to create the noise pattern.

Open GIMP
Make a blank image something like 800x600
Filter -> Cloud/noise it at maximum
save it
open it in Photoshop (the copy/paste seems to not work between the two programs)
go to Edit -> Define Pattern...
go back to your map
set your blurred-map-shape layer to "Multiply"
create a new layer underneath it
now use the bucket, set to "Pattern", and fill. (i actually applied it as a Layer Style, so that I could adjust the pattern scale)
Ctrl+U to adjust the lightness, bringing it up so that the darkest grey is around 25%.
merge the two layers
go to Edit->Adjustments->Threshold

it takes some trial-and-error, with the amount of blurr to your map-shape, the scale of the clouds, lightness of the clouds, and the threshold slider. just give it a few goes.