Choose interpreter after script start e.g. if/else inside hashbang

You can always make a wrapper script to find the correct interpreter for the actual program:

#!/bin/bash
if something ; then
    interpreter=this
    script=/some/path/to/program.real
    flags=()
else
    interpreter=that
    script=/other/path/to/program.real
    flags=(-x -y)
fi
exec "$interpreter" "${flags[@]}" "$script" "$@"

Save the wrapper in the users' PATH as program and put the actual program aside or with another name.

I used #!/bin/bash in the hashbang because of the flags array. If you don't need to store a variable number of flags or such and can do without it, the script should work portably with #!/bin/sh.

No, that won't work. The two characters #! absolutely needs to be the first two characters in the file (how would you specify what interpreted the if-statement anyway?). This constitutes the "magic number" that the exec() family of functions detects when they determine whether a file that they are about to execute is a script (which needs an interpreter) or a binary file (which doesn't).

The format of the shebang line is quite strict. It needs to have an absolute path to an interpreter and at most one argument to it.

What you can do is to use env:

#!/usr/bin/env interpreter

Now, the path to env is usually /usr/bin/env, but technically that's no guarantee.

This allows you to adjust the PATH environment variable on each system so that interpreter (be it bash, python or perl or whatever you have) is found.

A downside with this approach is that it will be impossible to portably pass an argument to the interpreter.

This means that

#!/usr/bin/env awk -f

and

#!/usr/bin/env sed -f

is unlikely to work on some systems.

Another obvious approach is to use GNU autotools (or some simpler templating system) to find the interpreter and place the correct path into the file in a ./configure step, which would be run upon installing the script on each system.

One could also resort to running the script with an explicit interpreter, but that's obviously what you're trying to avoid:

$ sed -f script.sed

You can also write a polyglot (combine two languages). /bin/sh is guaranteed to exist.

This has the downside of ugly code and perhaps some /bin/shs could potentially get confused. But it can be used when env does not exist or exists somewhere else than /usr/bin/env. It can also be used if you want to do some pretty fancy selection.

The first part of the script determines which interpreter to use when run with /bin/sh as interpreter, but is ignored when run by the correct interpreter. Use exec to prevent the shell from running more than the first part.

Python example:

#!/bin/sh
'''
' 2>/dev/null
# Python thinks this is a string, docstring unfortunately.
# The shell has just tried running the <newline> program.
find_best_python ()
{
    for candidate in pypy3 pypy python3 python; do
        if [ -n "$(which $candidate)" ]; then
            echo $candidate
            return
        fi
    done
    echo "Can't find any Python" >/dev/stderr
    exit 1
}
interpreter="$(find_best_python)"   # Replace with something fancier.
# Run the rest of the script
exec "$interpreter" "$0" "$@"
'''