I bought 2 years ago (Summer 2003) a SONY VAIO Z1A notebook computer.
About a year ago, I started occasionally seeing red line moving across
the screen and blocks of different colored pixels around cursor and
icons. When I connect an external monitor, I see the same patterns.
This rules out a problem with the screen and implicates the graphics
card (ATi Mobility Radeon 16MB integrated graphics). Here's the
question: is it worthwile or possible to replace or upgrade the
graphics card without motherboard replacement without costing close to
the costs of new notebooks?

All notebooks sold in the past, and even 99% of the current ones, have
integrated chips, which cannot be removed (soldered right onto the
main board, and pretty surgically too, don't mess with it!).
PCI-Express cards  for notebooks are a novelty right now (modular,
just like the memory, so you can remove it quite easily), so for now,
the rule of thumb is, you can NEVER do anything about your VGA part of
your notebook.