Batch create image contact sheet from videofiles?

I have a large amount of TV recordings made with a DVB tv-card. The files are .mpg and in most cases 2+ GB in size. The collection is large enough for me to need a good catalog system. I have a text index but recently got the idea of also making a contact sheet image for each video. By contact sheet I mean one image which contains a mosaic of many small thumbnail images from different parts of the video file. That provides a quick visual overview of the video.

I've recently made a few such contact sheets through a many-steps-process: I manually make screenshots in the application I use to also trim the video (commercial breaks and so on) before archiving it. After that, I use ACDSee to create a contact sheet out of the images.

Now I'm searching for a way to automate contact sheet creation from videos into a simple batch process.

So I want an application with these features:

1. read a video file and make screencaps
 - formats to handle: .mpg and ideally other formats like xvid .avi, .wmv ...
 - interval screencaps: I want a coherent contact sheet format and so want a sure way to get at least X number of screencaps (let's say 30) from any video regardless of it's length. So a "screencap every N seconds" setting might need to be complemented by a "screencap at every 1/N time segment of video".
 - timestamped screencaps: add a (customizable) timestamp to each screencap
(I understand that many automatic screenshots will be less useful than those taken manually but if I make many screencaps some of them will probably still give a good overview of the video.)

2. make contact sheet from screencaps
 - add a user customizable title/header for the contact sheet. Allow variables in header. Example: "$filename -- $year-$month-$day"
 - customizability for the amount of thumbnails, number os rows/lines, size of thumbnails, borders, background ...

3. saving
 - automatically save the generated contact sheet to some preset folder. Allow variables in filename just like for header/title above.
 
4. batch capabilities
 - run 1-3 over a set files/folders.
 - Or at the very least, allow complete command line control so that users can make external scripts to get such batch capabilities.
4 is important for me since I don't have the time to manually or even semi-manually make contact sheets for all older videos.

Can anyone recommend a tool that does all that? Or something that comes close? All suggestions are welcome!