Can I execute a Linux binary without the execute permission bit being set?

You can use /lib/ld*.so as an ELF interpreter, like so:

$ cp /bin/ls /tmp/ls
$ chmod a-x /tmp/ls
$ /lib/ld-linux.so.2 /tmp/ls

The actual name differs from architecture to architecture. Some names include /lib/ld-linux.so.2, /lib/ld-linux-x86-64.so.2 and /lib/ld-2.7.so. You can probably find it singularly as /lib/ld*.