Are my permissions for /usr/local/ correct?
I use Homebrew too and can confirm it's totally safe. Quoting the Installation page on the official Homebrew FAQ:


  Do yourself a favour and pick /usr/local
  
  
  It’s easier
  /usr/local/bin is already in your PATH.
  It’s easier
  Tons of build scripts break if their dependencies aren’t in either /usr or /usr/local. We fix this for Homebrew formulas (although we don’t always test for it), but you’ll find that many RubyGems and Python setup scripts break which is something outside our control.
  It’s safe
  Apple has conformed to POSIX and left this directory for us. Which means there is no /usr/local directory by default, so there is no need to worry about messing up existing tools.
  
  
  If you plan to install gems that depend on brews then save yourself a bunch of hassle and install to /usr/local!
  
  It is not trivial to tell gem to look in non-standard directories for headers and dylibs. If you choose /usr/local, everything “just works!”


I'll just add that doing things as root is a very bad idea, so chowning /usr/local not only seems reasonable to me (it's not a system dir on OSX), but sane.

Your permissions are not correct (yet). Just run the command you listed and you're gonna be fine.

If you have other problems remember, the brew doctor can help you!