I think the root of your problem is that you don't really understand the distinction between a Terminal Emulator and a Shell and how Linux figure out how to start processes.
First, there is the "Terminal Emulator", in Gnome-based environment this is usually Gnome Terminal.
Then there is the "Shell", in Linux this is usually bash, although other shells are possible.
A "Shell" runs inside a "Terminal Emulator". This distinctions comes from the age of physical terminals, where a physical Terminal is the hardware that takes input, writes text in colors, etc and the Shell is a software that processes user command and manage other processes based on the given commands.
Nowadays, we have a general purpose screen that can display any images, so we no longer use a physical Terminal, but instead have "Terminal Emulators", a software that emulates the job of a physical terminals, and the Shell, which is still the same ole' shell as previously (well, modern shells does take advantage of being in a software terminal emulator such as not being limited by the physical limitation of a paper, etc but the divide remains).
A "Shell" does not always run inside a Terminal Emulator; there are also Graphical Shell, such as Nautilus (hint hint, Nautilus is the name of a marine creature with a big shell) or Windows Explorer (not to be confused with Internet Explorer).
In both a command line shell, e.g. bash, and a graphical shell, e.g. Nautilus, an executable is marked by having its execute bit set.
In a command line shell, you can use ls -l to view a file's permission bits, e.g. rwxrwxrwx means everyone can read/write/execute the program; rwxr-xr-- means the owner have full permission, people in the file's group can read and execute but not write, and other people can only read the file. In Nautilus, you can right click on a file > Properties > Permission tab. In the Permission properties page you can the file's permission similar to in the command line shell.
A file which has their execute bit set are treated as executable, and can be executed by doing ./filename (command line shell) or double clicking (graphical shell).
Last, there are a few other subtleties on how a shell executes a file. In most Linux shell, you can "execute" a script written in python/perl/php/bash that is not a compiled executable. Since these files are not natively compiled executable, they need an interpreter (e.g. python interpreter) to be executed. Unlike in Windows shell (Explorer), which figures out the interpreter to invoke through the file's extension; Linux shells figures out the correct interpreter by looking at the "hashbang" line that looks like this
#!/usr/bin/python
when a file's execute bit is set and the file has this hashbang line, the shell will invoke the interpreter /usr/bin/python with the current file as the argument.
Nautilus can also recognize when a program is a command-line application, and will offer you to run the application inside a Terminal. When you double click an executable script, Nautilus will ask whether you want to run it in a Terminal, run without Terminal, or edit the file in a Text Editor.
