Open Terminal, and run the following:
This will download and install the Command Line Tools package and fix the problem.
You do not need Xcode, you can install only the Command Line Tools here, it is about 130Mb.
If the above alone doesn't do it, then also run:
sudo xcode-select --reset
The problem is that one needs to explicitly agree to the license agreement. As a follow on step, you may need to reset the path to Xcode if you have several versions or want the command line tools to run without Xcode.
sudo xcode-select --switch /Applications/Xcode.app
sudo xcode-select --switch /Library/Developer/CommandLineTools
I found the solution in this question, Command Line Tools not working.
You may get an error message: "Can't install the software because it is not currently available from the Software Update server". In this case
xcode-select --reset works as pointed by akozin.