Question 1, like BAR-CODE said dig through all the tuts till you find a few you understand.
Question 2, depends on your budget there are free 3d modeling apps. out there Blender seems to be pretty popular. I have 3ds Max and learned to use it in collage, basic modeling character modeling, and architectural visualization, and there is a lot I want to learn. I couldnt imagine have to learn 3d modeling be trial and error. Question 3, Once you learn the basics of modeling, basicly you import the characters mesh into your 3d modeling app and build the clothes around them. Question 4, A headband would be relatively simple, but if theres an easy way to model good clothing I havent stumbled on it yet. For me the hard part is getting the clothing Ive made to conform like it should.

Good Luck