In some cases, it's close to impossible (at the very least extremely impractical).
Typically, the best option is to use something from a "backports" type repository where someone else already figured out how to make the program compile against the old libraries.
Additionally you can try using something like Autopackage
which try to package all the needed libraries with each program you install. That way you don't have the dependency problems. You suffer in speed though because you're not sharing libraries (they get loaded once for say the desktop, and then again for the application).
Short of that, I run Debian and upgrading has been pretty easy (I've successfully dist-upgraded from Woody --> Sarge --> Etch without any problems) on my old box, a Celeron 400 MHz w/ 256MB RAM. The trick is to keep the bloat down and only install the packages I need. That way I can just install fairly current software when I need it...