Installing Xcode Command Line Tools
Apparently, there is some distinction between the command line tools installed for use by Xcode and the tools installed for system-wide use:


https://github.com/Homebrew/brew/issues/5002#issuecomment-425707878


For my machine, running xcode-select --install and choosing to install the tools from the window that popped up helped fix the problem. I was able to confirm that it was fixed when running brew config and seeing a valid entry for CLT:

macOS: 10.14-x86_64
CLT: 10.0.0.0.1.1535735448
Xcode: 10.0