How to use gcc or git without installing xcode?

No you don't, at least not anymore. The possibility mentioned by @jherran involves installing yet another piece of software. If that's ok with you, you can use Hombrew or Macports. Its controversial which one is 'better', so take which one you like.

But, since OSX Yosemite (or maybe earlier, not sure), the Command Line Tools can be installed separately, which is great since it allowed me to ditch the huge useless XCode app sitting idly on my hard drive. The most straightforward way might be to simply download the right package from Apple here.

When issuing the commands you mentioned, does a window pop up prompting you to install the Command Line Tools? It is outlined here that this is what should happen.

Or, just try to run

xcode-select --install

Which should do what you want. They can be updated via the App store, at least on Yosemite.

Note that if the executables are present in /usr/bin, you should be able to call them with their full name, e.g. /usr/bin/git.

You could install both of them using Homebrew:

brew install gcc
brew install git

To install homebrew, you just need this single command:

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Anyway, if you want to use git and gcc installed on you system, you don't need to install Xcode, instead you just need to install the command line developer tools, that you can install by typing: