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.