Easy fix: Don't investigate this sort of crime at all. That's a semi-serious suggestion, since Interpol are presumably putting up this picture because they don't think there's any chance of identifying this guy from the billion or so possibilities. If this doesn't work, they'll have to give up.
Instead, they are going to use the general public as a massively parallel matching machine, grind that billion or so down to a few thousand (?) possibilities, at which point more traditional detective work might be able to take over.
Others have made the point that involving Joe public at this stage risks vigilante action, to an extent that might outweigh the advantages of finding this person.
My point was to wonder whether the passport picture database (that I imagine most governments now maintain) could be used instead of the combined memories of the general public. That avoids the vigilante risk entirely, but I've no idea whether the idea is feasible, yet. (I'm sure it will be, one day soon, with all the civil liberty issues that entails.)