Actually they don't mean quite the same thing, even the ones that use the same phrase, though I can understand the confusion.
For all his complaining, I think he actually enjoyed the day.
Here for all means despite or regardless of. Even though he complained (which would imply he didn't enjoy the day), I still think he did enjoy it.
For all the trouble he's caused her, you'd think she'd be happy to see him go.
Here for all means considering, or taking into account. Given the fact that he's caused her so much trouble, it would be logical she'd be happy to see him go; but in fact she is not happy to see him go.
With all this uncertainty about jobs, it's difficult to make plans.
This with all is similar to the previous for all, and actually I think I'd prefer to use with all in both cases. With all here means considering or taking into account, just like before. You could also say it means since it's the case that.... Given the fact that there's so much uncertainty about jobs, making plans is difficult.
With all its faults, democracy is still the best system we have.
This one is similar to your first for all example. It means despite or regardless of. Even though democracy has many faults, it's still the best system we have.
So 1 and 4 are similar, and 2 and 3 are similar, even though they use different phrasing.