I have run up against that 4GB limit with my card... using just a Genesis 3 figure and some weighty clothing (vendors using lots of big maps and normal maps and all that jazz). I need a Titan of some kind...

As to whether or not it is difficult...how comfortable are you opening up the PC and adding a card? If you can do that, you've got the hard part covered. You might want to go in there and see if you can fit two video cards....and have enough power to run them both. Some of those cards are big. I've got some older cards I would love to stick in my machine just to be able to use the main one for Iray, but there's no room.

And no, you would not need to re-install your OS.