OK, well, I can't answer right off the bat why it isn't working. You could give us some more detail. I also can't leave a comment due to lack of rep here (despite my rep on other stack exchange sites). So I'll at least try to make this an answer.
First of all, if you are in fact using zsh, ~/.profile, and all the bash rc files are irrelevant. Go ahead and focus on .zshrc. That will be the correct rc file the majority of the time for this kind of stuff.
This kind of stuff generally "just works", so I'm inclined to speculate there's some part of the process you're not understanding, or missing.
First of all, ensure you are, in fact, using zsh:
echo $SHELL
echo $0
Share this output, please.
Secondly, verify that things are, in fact, not working. You should have already posted the output of:
echo $PATH
Try this before and after running the export ...
command. That's the only way to check that something else isn't going on.
A couple asides: restarts are irrelevant. If you put this stuff in your .zshrc, simply opening a new shell will suffice. Also, it might be easier to experiment by running these commands in an active shell, and not add them to your .zshrc file until you've resolved the issue.
Share the results of this and I'll get back to you.