Focus less on the program and more on learning technique. Pick any program, does not matter at all.
Secondly, if you are going to create head textures with a mouse, i suggest going down the cartoon/vector art route. In this case, you might want to pick a program that allows you to use a pen tool, helps.
Thirdly, youtube. Youtube what you need to know at that moment. For example "How to make a square in gimp" Youtube it, learn it, apply it, repeat. Keep doing this, build up knowledge, experiment.
There is no short cut, you just have to practice over and over. Having a tablet makes things a lot easier, but even then you still need to apply practice or you will not achieve your end goal.
Bottom line: Pick a program and start practicing.