Firstly, you don't need to install Xcode. The Git installer works perfectly well. However, if you want to use Git from within Xcode - it expects to find an installation under /usr/local/bin. If you have your own Git installed elsewhere - I've got a script that fixes this.
Second is to do with the path. My Git path used to be kept under /etc/paths.d/ However, a Mac OS X v10.7 (Lion) install overwrites the contents of this folder and the /etc/paths file as well. That's what happened to me and I got the same error. Recreating the path file fixed the problem.