Certain upgrades are possible, but it’s not that simple.
Accelerate your Mac is a nice source of information, you can find them here.
ANandtech did change the CPU of a Mac Pro.
OWC Mac Sales does have memory upgrades (there are others).
Video card: Unless you want to experiment with modified firmwares, your only choice in that model is the ATI 4870, which is considerably faster than the regular NVidia (it’s very noticeable in x-plane and 3d applications) but still lagging behind the “latest offerings”.
According to Wikipedia: "The Mac Pro, as with other Macintosh platforms, requires Mac OS X firmware. That is to say, a PCIe video card designed exclusively for other operating systems will not work properly under Mac OS X without appropriate drivers and/or firmware”
Sadly, no other video card has that, other than the Apple’s offerings. But If you google around there are some posts about people who managed to make other cards work.
Forget about upgrading your Motherboard, as it’s a custom design.
Hard drives/SuperDrives are generic and can be replaced, as you may have already guessed.
Any other component is probably “custom” designed for a Mac Pro (the power supply for example) and you won’t be able to get away with it…
Is it worth?
I have an early 2008 Mac Pro with 2x4 Intel XEON 2.8 and 10GB RAM. I’ve upgraded the RAM (from the lame 2GB to 10 @ OWC liked above), and I ordered the machine with the NVIDIA card (8800? I don’t remember), which was the only option other than the stock ATI2600 or something lame like that.
A couple of years later, the NVIDIA died (the Apple guy told me it had bugs and used to fail), so I got the new ATI 4780 512MB (it was 100€ less expensive than the out of warranty NVIDIA apple replacement). The difference was really noticeable in 3d apps.
I haven’t thought about upgrading the CPUs because getting faster XEONs (I wouldn’t be able to upgrade to Nehalem or anything new) won’t really make a big difference for me.
I use a SSD and 4 Hard Drives in the bays, if that counts as an upgrade (my original drive was 750gb, up from the stock 500).
I brought it with the Bluetooth/Wifi module (it was optional back then) and tho I haven’t used it a lot, it came in handy in a few occasions.
OS X Doesn’t support SLI/Crossfire for using more than 1 video card in parallel (you can install more than one, but it’s not the same thing), so forget about getting two super video cards for running crysis y super-top-ultra-maximum quality.
Conclusion
Yes, if you upgrade the RAM to something other than the 2GB and yes to the video card if you do 3d intensive stuff. Exposé will work fine on the NVIDIA8800 you have, but X-Plane (among other 3D things) will be noticeably faster with a new video card.
It does sound like the graphics card is failing. The garbled display is a symptom of this.
If you only run Windows, any PC graphics card in your Mac Pro will work fine.
What's more, the PC Radeon 58xx and 68xx cards work in OS X too, out of the box.
I would recommend one of Radeon 5850, 5870, 6850 or 6870 if you want Mac compatibility, or any good graphics card within your budget if you only want to game in Windows.
Best Answer
Yes, yes you can (although it may involve a firmware upgrade):
http://www.ifixit.com/Guide/iMac+Intel+20-Inch+EMC+2133+and+2210+Video+Card+Replacement/1014
(Taken from: http://www.ifixit.com/Answers/View/90234/Can+I+change+my+graphics+card)