If you have a relatively new monitor (1996 or later) that supports the PnP specification, there is a chance that you use the read-edid program to ask the monitor for its stastics and compute a mode line for you. See http://altern.org/vii/programs/linux/read-edid/.
Starting with XFree86 3.2, XFree86 provides an XF86Setup program that makes it easy to generate a working monitor mode interactively, without messing with video timing number directly. So you shouldn't actually need to calculate a base monitor mode in most cases. Unfortunately, XF86Setup has some limitations; it only knows about standard video modes up to 1280x1024. If you have a very high-performance monitor capable of 1600x1200 or more you will still have to compute your base monitor mode yourself.
There is a KDE tool called KVideoGen that computes modelines from basic monitor and card statistics. I've experimented with generating modelines from it, but haven't tried them in live use. Note that its horizontal and vertical `refresh rate' parameters are the same as the sync frequencies HSF and VSF we describe below. The `horizontal sync pulse' number seems to be a sync pulse width in microseconds, HSP (with the tool assuming fixed `front porch' HGT1 and `back porch' HGT2 values). If you don't know the `horizontal sync pulse' number it's safe to use the default.
Another XFree86 modeline generator lives here. You can either download the Python script or use the CGI form provided.
Recent versions of XFree86 provide a tool called xvidtune which you will probably find quite useful for testing and tuning monitor modes. It begins with a gruesome warning about the possible consequences of mistakes with it. If you pay careful attention to this document and learn what is behind the pretty numbers in xvidtune's boxes, you will become able to use xvidtune effectively and with confidence.
If you have xvidtune(1), you'll be able to test new modes on the fly, without modifying your X configuration files or even rebooting your X server. Otherwise, XFree86 allows you to hot-key between different modes defined in Xconfig (see XFree86.man for details). Use this capabilty to save yourself hassles! When you want to test a new mode, give it a unique mode label and add it to the end of your hot-key list. Leave a known-good mode as the default to fall back on if the test mode doesn't work.
Towards the end of this document, we include a `modeplot' script that you can use to produce an analog graph of available modes. This is not directly helpful for generating modelines, but it may help you better understand the relationships that define them.