First, check to see whether your TV has a Game mode--basically, a display mode that turns off postprocessing routines at the cost of a slight reduction in image quality. You might have to muck around in the manual to figure out exactly what it does--some manufacturers incorporate an Overdrive mode that may actually increase input lag.
Next, turn off as many other video-processing options as you can. Each manufacturer tends to identify its features with different acronyms such as DRE or 3DNR; try turning them off and seeing whether your lag improves.
If you use HDMI or component cables to connect your setup to your display, try using VGA instead. Display manufacturers sometimes restrict the postprocessing functions to HDMI or component video inputs, leaving the VGA input untouched. If your device doesn't have a proprietary VGA cable, you could try using an HDfury, though we haven't tested it in-house yet.
Finally, some apps and games have their own built-in latency calibration options. Both Rock Band and Guitar Hero, for example, include lag calibration functions as menu options to help you adjust the game's timing and to minimize lag. If these games are incorrectly calibrated, the faulty setting could be causing input lag, so be sure to test the settings before you try to play that fret-melting song.