If you don't absolutely need 4 colour palette options for your pattern, you can use one of those options as a "dirt" or "grunge" layer. Usually people offer both clean and dirty versions of their patterns if they do a dirty version (since dirt can't be turned off, just minimized by changing its colour to match the rest of the pattern) but it's quite easy to add dirt, and a lot of downloaders love having grungy icky unclean run-down houses.
Remember, when creating patterns, white is fully opaque, and black is fully transparent. So what we need to do is create a random, blotchy sort of image that's mostly black with some very dark grey and a few areas that are lighter, but not fully white.
The easiest way to do this is to use a simple filter. In Photoshop, try Filter - Render - Clouds. This automatically creates a seamless texture. You can then adjust the brightness and contrast so it's mostly dark with a few light-ish areas.
Of course, you don't have to use clouds - you can use any natural random looking texture that's seamless and has good variation between light and dark.
I'll cover a little more on handling of dirt layers in the Pattern Packager in the section on packaging up your pattern for use in-game.