My question is, with LibGDX's given library, is there a way I could copy Notch's Minicraft attempt at saving the images as grayscale, and just applying colors at runtime?
Are you using a SpriteBatch to render your characters? If you simply to batch.setColor(color) the texture you render after that will be tinted in the color you specify. Thats what I use for these kinds of customizations, works like a charm.
One trick (that I never used, but it should work) is to render your characters to the screen (without swapping the buffers so nothing is shown) and then copying the rendered character to a Texture e.g. using the ScreenUtils