Digital Mattes
While working at Image Arts Etc. I had the opportunity to create and experiment with digital mattes. Some simple and others becoming more complex and creative. One of the most important things you will need is your creativity; second, some good high res texture files. Different cloth and destroyed images produce some great mattes, although solid color mattes will work as well (no texture files needed).
One way of creating an interesting texture is to take an image, turn it black and white, then go extreme with Levels and Curves. Copy and paste the image, play with opacity and blending modes. These are some ideas which will hopefully help you get the creativity flowing and create some good texture files.
[Look for the doc I wrote while at Image Arts. Have a simple version and an extended version]