However, if everything you're installing that depends on Homebrew-provided software is also installed through Homebrew, then it should work regardless of location (I say "should" because I suspect that not every single Homebrew formula has actually been tested with a non-/usr/local install path).
Personally, I stick with /usr/local both because I've never had a problem with it, and because that makes it easier when working with software that uses a default PATH (since /usr/local is usually put in these default PATHs). But if you have any concerns whatsoever, then by all means use a different install prefix.
Sadly, you are correct about "not every single Homebrew formula has actually been tested with a non-/usr/local install path". In fact, while there are many Homebrew formulas of great quality, my impression is that there are also m many of rather poor quality, with other problems in them. E.g. just yesterday, I discovered that the Homebreak lmdb formula does not build properly versioned shared libraries -- because upstream didn't, and the packager either didn't notice or didn't care to fix it
I rarely (if ever) this kind of issue with MacPort and Fink, which try hard to avoid such problems (at the cost of a higher entry barrier for packagers -- for better or worse). Mind you, I am not everything is golden with them, either.
Disclaimer: I've been involved with the Fink project since OS X 10.1 or so.