This is to confirm that it's indeed possible to do the impossible - to upgrade an existing Debian Lenny i386 installation to amd64 in-place. I did it by roughly following the instructions in this document by Robin Lee Powell. Judging by the package versions mentioned there, I assume it has been written for some older version of Debian, but the basic steps still worked for me on Lenny.
At the same time I also confirm that all warnings and curse words in that document are there for a very good reason.
On installing the amd64 version of libc6 over i386 one the system ended up in a very broken state and I ended up picking together symlinks and ldconfig cache by hand from a static busybox shell. I'm thinking the breakage was because I had the optimized libc6-i686 installed, but I'm not sure - in the end there were something like 4 different binaries the /lib/libc.so.6 link could point to. Here I should mention that the default busybox package in Debian isn't statically built - that's in a separate package called busybox-static.
libc6 upgrade also broke hostname resolution, which I fixed after much digging around by changing the hosts: line in /etc/nsswitch.conf to:
hosts: files dns
It's also worth mentioning that until the very end of the procedure, it was impossible to get a new console login.
After I resolved that, it was pretty smooth sailing. I used aptitude instead of apt-get for the final step, which was much less painful. The only interesting thing was that the old i386 packages in apitude appeared as uninstalled, while dpkg showed them as installed. This caused some problems when installing conflicting packages, but nothing that couldn't be resolved by manually running dpkg.
Oh and instead of downloading those basic amd64 packages and all their dependencies by hand with a web browser, I simply downloaded a small CD ISO and kept it mounted somewhere, which proved very handy.
In conclusion, while this is possible, it's more akin to Linux from Scratch than something you would want to do regularly. I'm pretty certain that if the same situation arises again, I will choose to do a clean reinstall. But it was a fun exercise in Debian system administration and the experience might help the next time I'm on a system where 'ls' segfaults.