Hence the dilemma of needing to set an executable bit on an executable.
Windows gets around this because they just look for the .exe extension, Mac OS X gets around this because they can ship real disk images with the executable bit set. Linux is...lacking for a decent solution at the moment. makeself gets around this by wrapping your installer in a self-extracting shell script and praying that the desktop does the right thing when you click it but that has a different set of problems.
Eventually this will need a better solution that involves improvements at the distro layer.