brew doctor Warning: How to add git to PATH?

I installed Homebrew on OS X El Capitan. In the last steps of the installation I was supposed to install git with

brew install git

which was fine. Now if I run 'brew doctor' this happens:

$ brew doctor
Please note that these warnings are just used to help the Homebrew maintainers
with debugging if you file an issue. If everything you use Homebrew for is
working fine: please don't worry and just ignore them. Thanks!

Warning: Git could not be found in your PATH.
Homebrew uses Git for several internal functions, and some formulae use Git
checkouts instead of stable tarballs. You may want to install Git:
  brew install git

If I run 'brew install git' again, I get:

$ brew install git 
Warning: git-2.7.4 already installed

So needless to say my git version is 2.7.4. 'brew update' throws:

$ brew update
Warning: git-2.7.4 already installed
Error: Git must be installed and in your PATH!

Question: How do I fix my PATH so git can be found in my PATH and 'brew doctor' results in 'Your system is ready to brew'?

---

Additional Information:

• which -a git results in:

  $ which -a git
  /usr/local/bin/git
  /usr/local/bin/git
  /usr/bin/git
  

• I tried a lot of potential fixes, meanwhile I executed:

  echo 'export PATH="/usr/local/bin:$PATH"' >> ~/.bash_profile
  

  My ~/.bash_profile now looks like this:

  # Setting PATH for Python 2.7
  # The orginal version is saved in .bash_profile.pysave
  PATH="/Library/Frameworks/Python.framework/Versions/2.7/bin:${PATH}"
  export PATH=/usr/local/bin:$PATH
  

• When I try to install cask:

  $ brew tap caskroom/cask
  ==> Installing git
  Warning: git-2.7.4 already installed
  Error: Git is unavailable
  

• brew config:

  $ brew config
  HOMEBREW_VERSION: 0.9.5
  ORIGIN: (none)
  HEAD: (none)
  Last commit: never
  HOMEBREW_PREFIX: /usr/local
  HOMEBREW_REPOSITORY: /usr/local
  HOMEBREW_CELLAR: /usr/local/Cellar
  HOMEBREW_BOTTLE_DOMAIN: https://homebrew.bintray.com
  CPU: quad-core 64-bit haswell
  OS X: 10.11.4-x86_64
  Xcode: 7.3
  CLT: 7.3.0.0.1.1457485338
  Clang: 7.3 build 703
  X11: N/A
  System Ruby: 2.0.0-p648
  Perl: /usr/bin/perl
  Python: /usr/local/bin/python => /usr/local/Cellar/python/2.7.11/Frameworks/Python.framework/Versions/2.7/bin/python2.7
  Ruby: /usr/bin/ruby => /System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/ruby
  Java: 1.8.0_40
  

EDIT: Added cask to additional information.

EDIT2: Added brew config and added brew doctor prefix

First, change directory to /usr/local/Homebrew in the Terminal (for older versions of MacOS, use cd /usr/local/Library/Homebrew). Then run this:

git pull origin master
brew update && brew upgrade