If you have an Intel chipset, such as the built-in HD4000 graphics that come with Ivy Bridge CPUs, there are a few angles you can try that center around using xrandr, which stands for 'X Resize, Rotate and Reflection.' This program has a bunch of different options, and I strongly recommend spending some time with the man page. No matter which options you try first, you'll need to query the program and see which display device is being used. You can do this by typing into a terminal:
xrandr -q
For me, HDMI3 is the one that's hooked up, so it lists all of the available modelines and some other information.
Now that we know which device is being used, we can invoke xrandr with this syntax:
xrandr --output [device] --[option]
The option that worked for me is --transform, which performs some crazy matrix math that I don't understand (I'll update this post if someone tells me wtf is going on) on each pixel, apparently kinda like the pixel shader stuff I've written about elsewhere, I think...? Anyway (replace HDMI3 with whatever your device is called):
xrandr --output HDMI3 --transform 1.05,0,-35,0,1.05,-19,0,0,1
This doesn't make it fit exactly on my screen but it's much closer than it was. Unfortunately, it gets wiped out every time you logout, so we need to do something to make it stick. You can add it to your startup items or tack it onto your lightdm window manager's configuration file by typing into a terminal:
sudo nano /etc/lightdm/lightdm.conf
Navigate to the end of the file and start a new line and paste this in:
display-setup-script=xrandr --output HDMI3 --transform 1.05,0,-35,0,1.05,-19,0,0,1
Save and exit and the transform command should kick in every time you login.
Other options that may help:
The 'scale' option should ideally just scale your screen down, but in my experience, it makes everything (text, window borders , etc) bigger, similar to changing the DPI in Windows, without actually changing the visible area.
The 'border' option also seems like it should do exactly what we want, but I haven't seen it actually work anywhere. On my system, it fails with this error:
X Error of failed request: BadName (named color or font does not exist)
Major opcode of failed request: 140 (RANDR)
Minor opcode of failed request: 11 (RRQueryOutputProperty)
Serial number of failed request: 29
Current serial number in output stream: 29
which seems to be a catch-all for unrecognized commands :/
Generally, I would recommend skipping all of this and attempting to fix it through your TV's built-in options (generally called "just scan" mode or "pixel perfect" or something like that). The only time you should attempt to do it in software is when your TV is too crummy (like mine) and doesn't have any of those options.
UPDATE (5/20/2014): A helpful anonymous commentor explains the transform matrix thusly:
The transformation matrix seems pretty straightforward to me:
It's just an affine 2D transform. Think of 1.05,0,-35,0,1.05,-19,0,0,1 as the following matrix:
|1.05 0 -35|
|0 1.05 -19|
|0 0 0 |
The upper two diagonal coefficients are scaling factors, i.e. in this case, the picture would be expanded by 5% horizontally and vertically. The last column is a translation vector, in this case causing the picture to be transformed by 35 pixels to the left and 19 pixels upwards (or downwards, depending on the coordinate system).
The last row needs to be (0, 0, 1), or combining two affine transforms will not work correctly. They are not relevant for the actual transformation.
