Look up OS X release.
there$ sw_vers -productVersion
10.9.5
Go to https://developer.apple.com/downloads/ and get the best release of Command Line Tools for Xcode. For example, the latest version for OS X 10.9 is http://adcdownload.apple.com/Developer_Tools/Command_Line_Tools_OS_X_10.9_for_Xcode__Xcode_6.2/commandlinetoolsosx10.9forxcode6.2.dmg.
After downloading the DMG, run the script to extract the PKG file, copy it to the remote host, and install everything.
here:Downloads$ ./remote-headless-brew.sh me@there [commandlinetools*.dmg]
Hrmm...think I need to work a
sudo xcodebuild -license
into teh process nowadays.