making proprietary ELF binaries portable on Linux

I am searching for a way to make existing proprietary ELF-binaries, which are linked against specific versions of system libraries, portable. With portable I mean making the executable work on every system with the same processor architecture and a compatible system kernel, without necessarily having the source code of the libraries (if there is no way without having the source code, it'll be fine too).

So far I thought of two possibilities, but I don't know if they are at all possible and if yes, which to choose:

Searching all linked libraries and their dependencies and include them in a subdirectory of the binary and changing the Library-Path to that directory.
Relinking the libraries statically into the binary file to one big executable (if the program doesn't verify itself based on a checksum).

Licensing is no issue as I don't want to distribute the created portable programs, it's for private use only.

Thanks for your answers.

Searching all linked libraries and their dependencies and include them in a subdirectory of the binary and changing the Library-Path to that directory.

This would work for most shared libraries, but will not work for libc.so.6 (which is the one most likely to give problems if your target system doesn't have new enough version).

The reason: glibc consists of over 200 separate shared libraries, which have un-versioned binary interfaces between them, and do not have a stable ABI between them. Because of this, all parts of glibc must come from the same build. One of these parts is libc.so.6. Another is ld-linux.so. An absolute path to the latter is hard coded into every dynamic executable. The end result: if you supply your own copy of libc.so.6, and if that copy doesn't match /lib/ld-linux*.so.2 present on the system, then you'll see very strange crashes which you would have very hard time to explain or debug.

Relinking the libraries statically into the binary file to one big executable.

That can't work on any UNIX system other than AIX: they all consider a.out and foo.so to be the final link product, which can't be linked any further.

There exists statifier, which does create a (huge) static executable out of a dynamic one. I have no experience using it.