There would be a step anyway between the user selecting even a regular binary executable (via pressing enter after writing its name on the shell, by double-clicking on it in a desktop file manager, by running a shell script which on some line invokes it, etc) and it starting to execute (the shell or GUI would have to interpret the action and tell the OS to execute the binary).
So adding an intermediary to do a choice of executor and/or handover in between (whereas at the shell/file-manager level, or at the OS call level), but still before execution, is quite easy.
It is not too different from the way in which html-pages can declare what is the character-set that should be used to interpret the binary contents of the file. The deep thing to me is that programs can not only encode instructions for the computer, they can also encode how to do the decoding. Obviously you then need some common convention (like shebang) to say how you can interpret the part that tells how to interpret the content.