Along with Hackbraten's answer — I don't know if this would be more or less work for you but would a per-user Homebrew installation help? I don't have any multi-user machines but for years I've kept my Homebrew installation in ~/Homebrew, where I have complete ownership of it. (Really you can install Homebrew in any directory) Or would the space/compilation cost be prohibitive?
Not a Homebrew maintainer, just a satisfied user.