you probably have a my.cnf file left over from an old installation. Homebrew doesn't make one by default so it must be something you've done (either a failed uninstall or maybe you created one trying to make it work). Check the usual locations /etc/my.cnf is typical but you may have put it somewhere else. Remove or rename it. Double check you've cleaned out any old'n'busted installations.
I took a couple of screenshots of my terminal showing how I reproduced your first error and how I figured out the cause and fixed it. Things I type are the colourful lines.
First lets just brew install (I already ran brew doctor and made sure all my software was up to date).
I changed into the mysql directory to see what version gets installed by homebrew.
cd /usr/local/Cellar/mysql/<version here="">/
Version was 5.5.28 when I wrote this.
So far so good. I wonder what happens if you just ignore the instructions and try to start up mysql…

I see, an error like the one you got. Excellent, so I've managed to get the same error message by doing what I suspected OP did. Okay, lets see what's up. The error says it didn't update a file - lets go see what's there…

No permissions? Maybe I need to be root.
Looks like it works. I wonder if I can start mysql as root…

(NOTE: I opened up a second terminal window here, the last command is provided for context)
No dice…
Lets see what's in the error file.
(NOTE: My computer's network name is Lucy - that's how I knew the name of the file to check. Yours will be named after your computer so change accordingly. when in doubt just LS and pick the appropriate file).

Looks like a permissions issue, is really the cause because that's what the error message says. Knowing how to reproduce the error and the likely cause - lets go back and do what homebrew told us 2 minutes ago. Maybe it does something to set correct ownership…
(NOTE: I went back to the first terminal window)

Nope, still getting an error.
Notice the line where I deleted the .err file. I did that so if there were problems starting mysql I could read the entire file and know that the contents covered everything after I had identified the likely cause of the problem. You shouldn't need to do this, but I'd recommend it for the same reason I did it.
Looks like there's still a permissions issue. I bet it has to do with that path from the error log. Lets change the owner to my usual user account (because that's what I'd run MySQL as) and try again (the fuzzy square boxes is just my short user name). Maybe ignoring the brew instructions made MySQL create paths with permissions that the install script doesn't know how to deal with.

That's promising. "Setting up tables" and the word "ok" is the sort of thing I'd expect to see if everything was working. I'm ignoring the "do this stuff to make it start on boot up" instructions because I don't want it to (I'm uninstall mysql because I think postgres is generally a better choice - this would just make extra work for me and doesn't have anything to do with your problem).

This one includes the last line as context along with the full set of instructions for setting up mysql to start up when you reboot. Let's try running mysql.server start.
Looks like fixing permissions was the solution. That might have been broken by not running the mysql_install_db script properly the first time, or it might be an issue with the recipe. Either way - looks like it works and mysql is running.</version>