What PSU should I get?

Corsair, Season, Silver Stone, OCZ are good brands to choose from they are more reliable then most others.

would 500 watt be enough for my set up if i got the gpu in the link?

You might want to get this
http://www.newegg.com/Product/Product.aspx?Item=N82E168...
Hoowever you might have to spend a bit more on the psu because it has a minimum 550 watt power supply. You also need a 8 pin power supply adapter (very cheap) and it is 2 inches longer than the one you posted. However, there is windforce 3x cooling, the clock speeds are higher (not by that much), and it is $70 cheaper. As for your psu there are certain ones you should avoid. This guide lists the good ones and is good for picking parts for your first build.
http://i1002.photobucket.com/albums/af150/The_FalconO6/...

It's not really my first build i'm just considering upgrading. If i just play with a single 1080p screen would 4GB VRAM be overkill?

Yes, 4gb would be overkill. No need for that much. Just stick with around 2gb. That's more than plenty.

for some mods, for example 2K textures for skyrim, it says you should have at least 2 or 3 GB+ in VRAM to download a complete retexture pack for skyrim. Would it be better to get faster clock speeds than VRAM though? Any 670 I get is sure to be a big upgrade from my 6870 anyways.

The gtx 670 and the hd 7970 will be able to handle that no problem. If you want, you can obviously wait and spend the extra money on the one you were originally gonna go with. I guess you could consider it a precaution. Or you could just take your pick between one of the gtx 670s I recommended or a hd 7970. All of these would be great options for playing skyrim w/ lots of mods.

On a single screen, even with all those mods I'd go with Gigabyte's version of the 2gb gtx 670 windforce.

GIGABYTE GV-N670OC-2GD GeForce GTX 670 2GB
http://www.newegg.com/Product/Product.aspx?Item=N82E168...

GIGABYTE GV-R797OC-3GD Radeon HD 7970 3GB
http://www.newegg.com/Product/Product.aspx?Item=N82E168...

Extra Vram is really only gonna help with multiple monitor setups.

OK thanks, i'll probably go with that gigabyte gtx 670. I'm going with Nvidia since some games I play like batman have special features if you use Nvidia. Plus the 670 looks like the best bang for the buck right now.

Indeed. Excellent choice. Good luck!

Best answer selected by timnswede.