Hi, I have Nvidia Geforce 5200 tvout to my television, which works very fine besides a large black border on the right, and a small one on the left.
I can use the nvidia-settings tool to increase overscan, and remove the borders, but at the cost of cuts in top and bottom.

Now is it possible to overscan only in one side (right side)? Perhaps using xorg.conf or something..
Based on threads found on google, I have tried to start xvidtune, drag some bars, and press Apply, but nothing seams to happen.

Can you help me?

I know what you mean when you say the overscan widens the picture, but then you lose the top/bottom.
Here's a suggestion:
This is some stuff from my xorg.conf file. I use two monitors.

Option "metamodes" "CRT-0: 1600x1200 , CRT-1: 1280x1024 @ 1600x1200"

Notice the @ 1600x1200 after the resolution for the CRT-1. This makes a 'virtual' size, which makes the displayed picture larger than the actual monitor screen. I do this so the smaller monitor (CRT-1) will contain the same size image as my CRT-0, but I scroll the screen to see the edges of the picture.
I figure you could apply the same principle to your TV, using some virtual dimensions to enlarge the displayed picture.
For example, you might use:

modes "1024x768 @ 1064x768"

to make the image 40 pixels wider, without changing the up/down height of the image.

Now, regardless of the above, here's how to move the image to the right to center it:

modes "1024x768 @ 1064x768 +20+0"

That will make the left edge of the picture begin 20 pixels further to the right, to even the borders (if any) on the left and right.

Maybe between the two ideas here, you can manipulate the image to a size and location that you are happy with?
Good luck, and let us know how it goes