> ftp://ftp.netbsd.org/pub/NetBSD/misc/junyoung/prebind-20020927.tar.gz

I looked at this a bit.  As I understand the code, it does two things:

1) It relocates the library to a different base address.  This is what
   I talked about before.  It should be fine.

2) It prebinds internal symbol references in the library.  This,
   unfortunately, is not okay.  It flagrantly violates the ELF dynamic
   linker semantics -- a symbol in an outer scope (e.g. the
   executable) must override the definition in an inner scope
   (e.g. libc).  That you break this is embodied in the fact that you
   have to hack around a few specific symbols.

So, I think this is not viable.  We should look at jakub's work on
Linux.