That sounds a lot like overscan - Where the TV makes the picture a tiny percentage larger then the display to make sure the content fills the screen -- it's probably not your computer's fault. Which is why no matter what res you choose, your TV's overscanning the picture to make sure the frame is filled with picture.
Firstly, try looking around in the TV's menu for Overscan or a PC Mode -- the Samsung panels I have at work when set in a PC mode will disable a lot of the dynamic color/gamma ramping, edge enhancement, and most importantly : overscan features.
In the nVidia drivers for Windows, there's a setting for overscan compensation where the video card is still sending 1920x1080, but is downscaling your 1920x1080 desktop to make up for the edges your TV is chopping off. It looks like this:
This isn't the best option since you're downsampling your desktop, then the TV's upsampling it again in the overscan function. It'd be best to see if you can just turn overscanning off in your TV.
The triangles let you tell the driver how much area is visible (and conversely, how much is chopped off).
I'm not sure how well it works in Linux, but here's some people talking about it, as well as screenshots of what it looks like: