How to properly and for once reinstall PHP/Apache

The brew commands look ok. You have all the taps you need.
First of all since you're working with homebrew, I'd suggest the following two commands (let's start clean):

brew update && brew cleanup

So we're sure that we're using the latest homebrew release and we cleanup all old formulas and leftovers.

From your PATH it looks like usr/bin (which is the standard Mac OS X path for binaries and executables) comes before usr/local/bin (the path in which homebrew links the Cellar).
As you might know, Mac OS X when looking for binaries/executables scans the PATH from top to bottom so if both usr/bin and usr/local/bin have the php executables, since usr/bin comes first in PATH, then Mac OS X will use the php version in such folder, ignoring the version in usr/local/bin (which, as instead, is our target).

To make sure regarding which version Mac OS X is using, type in the Terminal

which php

and if the output is usr/bin, then Mac OS X is using its own version.

The core indeed now is to change the PATH order in bash_profile, and make sure that usr/local/bin comes before usr/bin (it is clear now that we're forcing Mac OS X to use the homebrew version).

Once the changes have been done, restart your Mac and type in the Terminal

echo $PATH

This will display the entire PATH list so you can make sure everything's in the right order.
Now, finally, you can check using either

which php

or

php -v

which is the running version.