Building linux binaries for multiple platforms
You may try to focus on a few major platforms rather than individual distributions. What I mean by that is to build on what I call the "foundational distros" (Debian and RedHat) and hope for the best on the others.
Most likely, Debian binaries (that are statically linked) will run just fine on Ubuntu and Mint and other Debian derived distributions. RedHat binaries will probably run on Centos, Scientific Linux and SuSE Linux. If you care about less popular distros (Say you have a lot of customers running some uncommon Linux), and neither your Debian or RedHat executable works on them or can be made to work somehow, then setup a VM of that distro and build one executable specifically for that flavor.
I've taken this approach in the past and it has worked well.
The best way to do that it to make your software some open-source free software (e.g. GPLv3+ license), then if your software is interesting enough it will become packaged in distributions (by the distribution maintainer).
You always want to provide distribution packages (e.g. .deb files for Ubuntu or Debian) because these are the easiest to install.
If you still want to make proprietary software (but ask yourself if you will be able to sell, or even distribute gratis, successfully your software), you might take the following steps:
compile a recent GCC compiler (e.g. 4.8) by enabling a static stdc++ & a static libgcc (most distribution provided GCC don't do that).
link your program perhaps statically (but you might not be able to do this, e.g. for
/etc/nsswitch.confrelated functions, includinggetaddrinfoand related DNS services).
Even by linking all C++ related stuff statically you still depend on libc.so.6 and then you may have some Gnu Libc versioning issues (hence a binary compiled for a libc version 2.17 won't always run with a libc 2.16 or vice versa). Also notice that GNU libc are usually tied to some kernel version (you cannot use a recent libc on some quite old kernel). You could consider some alternative libc like MUSL libc
BTW, you usually can use some chroot-ed target environment (in which you might install some other distribution, eg. with debootstrap)
If anyone is curious we did solved the problem by building a GCC 4.8 toolchain on top of a RHEL 4.8 dist that continued to be our build agent.
The crux of it is outlined here. The problem was a little bit simpler since we don't need a fully functional cross compiler. Just a GCC 4.8 toolchain on the target host.
Interoperability was still a pain because this old version of Linux had virtually no support for SMB and/or other tech. We ended up with a Bash script that put build outputs in a FTP server and this worked reasonably well. It solved major pains.