Try using randomly jittered samples, à la Crysis (http://i246.photobucket.com/albums/gg90/desert-fox-/crysis2009-01-1422-25-23-04.jpg). Your shadows will look ok when you apply textures over the scene since they'll hide the noise fairly well.
Once you have jittered shadows, you can try to apply your screen space blur to remove the noise - that should result in a nice soft shadow.
Another option is to try VSM or ESM for your shadows - these techniques basically store info that can be blurred and filtered (variance in VSM case, pretty sure it something similar for ESM). Then you just blur it and apply (using the VSM/ESM apply functions of course, it's not a simple depth test anymore). That'll give you noise free, soft shadows.
Maybe google for some more examples/ideas from these techniques, I'm sure one will suit your needs.