Solution
Open Terminal, and run the following:
xcode-select --install
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:
xcode-select --reset
Further reading
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.
xcode-select --switch /Applications/Xcode.app
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.