Root is user 0
The key thing is the user ID 0. There are many places in the kernel that check the user ID of the calling process and grant permission to do something only if the user ID is 0.
The user name is irrelevant; the kernel doesn't even know about user names.
Android's permission mechanism is identical at the kernel level but completely different at the application level. Android has a root user (UID 0), just like any other system based on a Linux kernel. Android doesn't have user accounts though, and on most setups doesn't allow the user (as in the human operating and owning the device) to perform actions as the root user. A “rooted” Android is a setup that does allow the device owner/user to perform actions as root.
How setuid works
A setuid executable runs as the user who owns the executable. For example, su is setuid and owned by root, so when any user runs it, the process running su runs as the root user. The job of su is to verify that the user that calls it is allowed to use the root account, to run the specified command (or a shell if no command is specified) if this verification succeeds, and to exit if this verification fails. For example, su might ask the user to prove that they know the root password.
In more detail, a process has three user IDs: the effective UID, which is used for security checks; the real UID, which is used in a few privilege checks but is mainly useful as a backup of the original user ID, and the saved user ID which allows a process to temporarily switch its effective UID to the real user ID and then go back to the former effective UID (this is useful e.g. when a setuid program needs to access a file as the original user). Running a setuid executable sets the effective UID to the owner of executable and retains the real UID.
Running a setuid executable (and similar mechanisms, e.g. setgid) is the only way to elevate the privileges of a process. Pretty much everything else can only decrease the privileges of a process.
Beyond traditional Unix
Until now I described traditional Unix systems. All of this is true on a modern Linux system, but Linux brings several additional complications.
Linux has a capability system. Remember how I said that the kernel has many checks where only processes running as user ID 0 are allowed? In fact, each check gets its own capability (well, not quite, some checks use the same capability). For example, there's a capability for accessing raw network sockets, and another capability for rebooting the system. Each process has a set of capabilities along side its users and groups. The process passes the check if it is running as user 0 or if it has the capability that corresponds to the check. A process that requires a specific privilege can run as a non-root user but with the requisite capability; this limits the impact if the process has a security hole. An executable can be setcap to one or more capabilities: this is similar to setuid, but works on the process's capability set instead of the process's user ID. For example, ping only needs raw network sockets, so it can be setcap CAP_NET_RAW instead of setuid root.
Linux has several security modules, the best known being SELinux. Security modules introduce additional security checks, which can apply even to processes running as root. For example, it's possible (not easy!) to set up SELinux so as to run a process as user ID 0 but with so many restrictions that it can't actually do anything.
Linux has user namespaces. Inside the kernel, a user is in fact not just a user ID, but a pair consisting of a user ID and a namespace. Namespaces form a hierarchy: a child namespace refines permissions within its parent. The all-powerful user is user 0 in the root namespace. User 0 in a namespace has powers only inside that namespace. For example, user 0 in a user namespace can impersonate any user of that namespace; but from the outside all the processes in that namespace run as the same user.
Several reasons: one, you have to have physical access to the servers, and most employees don't want to lose their jobs by getting caught on CCTV video breaking into systems. Then, you have some companies that implement BIOS / boot passwords or boot loader passwords. Sometimes, the "single user" option requires a password (if set up properly ahead of time), other times it simply isn't available.
Ultimately, though, you're correct - this is a very exploitable attack vector.
Best Answer
(I'll try to be brief.)
In theory, there are two dimensions of privileges:
The computer's instruction set architecture (ISA), which protects certain information and/or functions of the machine.
The operating system (OS) creating an eco-system for applications and communication. At its core is the kernel, a program that can run on the ISA with no dependencies of any kind.
Today's operating systems perform a lot of very different tasks so that we can use computers as we do today. In a very(, very, very) simplified view you can imagine the kernel as the only program that is executed by the computer. Applications, processes and users are all artefacts of the eco-system created by the OS and especially the kernel.
When we talk about user(space) privileges with respect to the operating system, we talk about privileges managed, granted and enforced by the operating system. For instance, file permissions restricting fetching data from a specific directory is enforced by the kernel. It looks at the some IDs assodicated with the file, interpretes some bits which represents privileges and then either fetches the data or refuses to do so.
The privileges hierarchy within the ISA provides the tools the kernel uses for its purposes. The specific details vary a lot, but in general there is the kernel mode, in which programs executed by the CPU are very free to perform I/O and use the instructions offered by the ISA and the user mode where I/O and instructions are constrained.
For instance, when reading the instruction to write data to a specific memory addres, a CPU in kernel mode could simply write data to a specific memory address, while in user mode it first performs a few checks to see if the memory address is in a range of allowed address to which data may be written. If it is determined that the address may not be written to, usually, the ISA will switch into kernel mode and start executing another instruction stream, which is a part of the kernel and it will do the right thing(TM).
That is one example for an enforcement strategy to ensure that one program does not interfere with another program ... so that the javascript on the webpage you are currently visiting cannot make your online banking application perform dubious transactions ...
Notice, in kernel mode nothing else is triggered to enforce the right thing, it is assumed the program running in kernel mode is doing the right thing. That's why in kernel mode nothing can force a program to adhere to the abstract rules and concepts of the OS's eco-system. That's why programs running in kernel mode are comparibly powerful as the root user.
Technically kernel mode is much more powerful than just being the root-user on your OS.