Nix uses rpaths on Linux (install names on OSX) to fix the precise location of dynamically linked dependencies, and it also patches the paths to executables (e.g. In string laterals or shebangs) needed at run time. To change the location of a binary, one would have to patch the dependents so that /nix/store is replaced with the new prefix, which is generally not possible to do, unless the new prefix has the same length as the old prefix - in which case you can just sed every file.

Homebrew just assumes that the needed executables will be available on $PATH and that the dynamic linker will find libs in /usr/lib or /usr/local/lib.

So yes, you really would need to recompile everything if change the prefix from /nix/store to something else.

Edits: fixed spelling and structure from originally typing via phone.