How to make Unix binary self-contained?

I have a Linux binary, without sources, that works on one machine, and I'd like to make a self-contained package that would run on a different machine of the same architecture. What is a way of achieving this?

In my case, both machines have the same architecture, same Ubuntu kernel, but target machine doesn't have make and has wrong version of files under /lib and /usr

One idea I had was to use chroot and recreate a subset of the filesystem that the binary uses, possibly using strace to figure out what it needs. Is there a tool that does this already?

For posterity, here's how I figure out which files a process opens

#!/usr/bin/python
# source of trace_fileopen.py
# Runs command and prints all files that have been successfully opened with mode O_RDONLY
# example: trace_fileopen.py ls -l
import re, sys, subprocess, os

if __name__=='__main__':
  strace_fn = '/tmp/strace.out'
  strace_re = re.compile(r'([^(]+?)\((.*)\)\s*=\s*(\S+?)\s+(.*)$')

  cmd = sys.argv[1]
  nowhere = open('/dev/null','w')#
  p = subprocess.Popen(['strace','-o', strace_fn]+sys.argv[1:], stdout=nowhere, stderr=nowhere)
  sts = os.waitpid(p.pid, 0)[1]

  output = []
  for line in open(strace_fn):
    # ignore lines like --- SIGCHLD (Child exited) @ 0 (0) ---
    if not strace_re.match(line):
      continue
    (function,args,returnval,msg) = strace_re.findall(line)[0]
    if function=='open' and returnval!='-1':
      (fname,mode)=args.split(',',1)
      if mode.strip()=='O_RDONLY':
        if fname.startswith('"') and fname.endswith('"') and len(fname)>=2:
          fname = fname[1:-1]
        output.append(fname)
  prev_line = ""
  for line in sorted(output):
    if line==prev_line:
      continue
    print line
    prev_line = line

Update The problem with LD_LIBRARY_PATH solutions is that /lib is hardcoded into interpreter and takes precedence over LD_LIBRARY_PATH, so native versions will get loaded first. The interpreter is hardcoded into the binary. One approach might be to patch the interpreter and run the binary as patched_interpreter mycommandline Problem is that when mycommandline is starts with java, this doesn't work because Java sets-up LD_LIBRARY_PATH and restarts itself, which resorts to the old interpreter. A solution that worked for me was to open the binary in the text editor, find the interpreter (/lib/ld-linux-x86-64.so.2), and replace it with same-length path to the patched interpreter