On SIP-enabled systems that can't really be done anymore. But on Linux (LinuxBrew) that can definitely happen. The brew link system is supposed to help with that, but there are no guarantees.
As someone who runs Linuxbrew, I can assure you it does no such thing unless someone is misguided enough to have "NOPASSWD: ALL" in sudoers. Filesystem permissions didn't magically stop existing because Linuxbrew showed up, and it does not use any setuid binaries
Keep in mind that /usr/local might contain user-created files and directories and might not have their permissions set strictly like other system directories. If you create something in there and then run brew, your normal user permissions are enough to silently overwrite things.
That said, brew is (usually) smart enough to notice if a file already exists, and it will simply leave it be and prompt the user. The problem at that point is that the force link command works without sudo and will happily overwrite anything with a symlink to the Cellar-installed version.