What exactly happens when I execute a file in my shell?

The definitive answer to "how programs get run" on Linux is the pair of articles on LWN.net titled, surprisingly enough, How programs get run and How programs get run: ELF binaries. The first article addresses scripts briefly. (Strictly speaking the definitive answer is in the source code, but these articles are easier to read and provide links to the source code.)

A little experimentation show that you pretty much got it right, and that the execution of a file containing a simple list of commands, without a shebang, needs to be handled by the shell. The execve(2) manpage contains source code for a test program, execve; we'll use that to see what happens without a shell. First, write a testscript, testscr1, containing

#!/bin/sh

pstree

and another one, testscr2, containing only

pstree

Make them both executable, and verify that they both run from a shell:

chmod u+x testscr[12]
./testscr1 | less
./testscr2 | less

Now try again, using execve (assuming you built it in the current directory):

./execve ./testscr1
./execve ./testscr2

testscr1 still runs, but testscr2 produces

execve: Exec format error

This shows that the shell handles testscr2 differently. It doesn't process the script itself though, it still uses /bin/sh to do that; this can be verified by piping testscr2 to less:

./testscr2 | less -ppstree

On my system, I get

    |-gnome-terminal--+-4*[zsh]
    |                 |-zsh-+-less
    |                 |     `-sh---pstree

As you can see, there's the shell I was using, zsh, which started less, and a second shell, plain sh (dash on my system), to run the script, which ran pstree. In zsh this is handled by zexecve in Src/exec.c: the shell uses execve(2) to try to run the command, and if that fails, it reads the file to see if it has a shebang, processing it accordingly (which the kernel will also have done), and if that fails it tries to run the file with sh, as long as it didn't read any zero byte from the file:

        for (t0 = 0; t0 != ct; t0++)
            if (!execvebuf[t0])
                break;
        if (t0 == ct) {
            argv[-1] = "sh";
            winch_unblock();
            execve("/bin/sh", argv - 1, newenvp);
        }

bash has the same behaviour, implemented in execute_cmd.c with a helpful comment (as pointed out by taliezin):

Execute a simple command that is hopefully defined in a disk file somewhere.

1. fork ()
2. connect pipes
3. look up the command
4. do redirections
5. execve ()
6. If the execve failed, see if the file has executable mode set. If so, and it isn't a directory, then execute its contents as a shell script.

POSIX defines a set of functions, known as the exec(3) functions, which wrap execve(2) and provide this functionality too; see muru's answer for details. On Linux at least these functions are implemented by the C library, not by the kernel.

In part, this depends on the particular exec family function that's used. execve, as Stephen Kitt has shown in detail, only runs files in the correct binary format or scripts that begin with a proper shebang.

However, execlp and execvp go one step further: if the shebang wasn't correct, the file is executed with /bin/sh on Linux. From man 3 exec:

Special semantics for execlp() and execvp()
   The execlp(), execvp(), and execvpe() functions duplicate the actions
   of the shell in searching for an executable file if the specified
   filename does not contain a slash (/) character.
   …

   If the header of a file isn't recognized (the attempted execve(2)
   failed with the error ENOEXEC), these functions will execute the
   shell (/bin/sh) with the path of the file as its first argument.  (If
   this attempt fails, no further searching is done.)

This is somewhat supported by POSIX (emphasis mine):

One potential source of confusion noted by the standard developers is over how the contents of a process image file affect the behavior of the exec family of functions. The following is a description of the actions taken:

1. If the process image file is a valid executable (in a format that is executable and valid and having appropriate privileges) for this system, then the system executes the file.

2. If the process image file has appropriate privileges and is in a format that is executable but not valid for this system (such as a recognized binary for another architecture), then this is an error and errno is set to [EINVAL] (see later RATIONALE on [EINVAL]).

3. If the process image file has appropriate privileges but is not otherwise recognized:

   1. If this is a call to execlp() or execvp(), then they invoke a command interpreter assuming that the process image file is a shell script.

   2. If this is not a call to execlp() or execvp(), then an error occurs and errno is set to [ENOEXEC].

This doesn't specify how the command interpreter is obtained, so, but doesn't specify that an error has to be given. I guess, therefore, that the Linux devs allowed such files to be run with /bin/sh (or this was already a common practice and they just followed suit).

FWIW, the FreeBSD manpage for exec(3) also mentions similar behaviour:

 Some of these functions have special semantics.

 The functions execlp(), execvp(), and execvP() will duplicate the actions
 of the shell in searching for an executable file if the specified file
 name does not contain a slash ``/'' character. 
 …
 If the header of a file is not recognized (the attempted execve()
 returned ENOEXEC), these functions will execute the shell with the path
 of the file as its first argument.  (If this attempt fails, no further
 searching is done.)

---

AFAICT, however, no common shell uses execlp or execvp directly, presumably for finer control over the environment. They all implement the same logic using execve.

This could be an addition to Stephen Kitt answer, as a comment from bash source in file execute_cmd.c:

Execute a simple command that is hopefully defined in a disk file somewhere.

1. fork ()
2. connect pipes
3. look up the command
4. do redirections
5. execve ()
6. If the execve failed, see if the file has executable mode set.  

If so, and it isn't a directory, then execute its contents as a shell script.