"No such file or directory" error when executing a binary

The answer is in this line of the output of readelf -a in the original question

  [Requesting program interpreter: /lib/ld-linux.so.2]

I was missing the /lib/ld-linux.so.2 file, which is needed to run 32-bit apps. The Ubuntu package that has this file is libc6-i386.

Old question, but hopefully this'll help someone else.

In my case I was using a toolchain on Ubuntu 12.04 that was built on Ubuntu 10.04 (requires GCC 4.1 to build). As most of the libraries have moved to multiarch dirs, it couldn't find ld.so. So, make a symlink for it.

Check required path:

$ readelf -a arm-linux-gnueabi-gcc | grep interpreter:
      [Requesting program interpreter: /lib/ld-linux-x86-64.so.2]

Create symlink:

$ sudo ln -s /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 /lib/ld-linux-x86-64.so.2

If you're on 32bit, it'll be i386-linux-gnu and not x86_64-linux-gnu.