Weight painting is going to give you major headaches with that model. There are so many intersecting pieces. In a way it’s kind of like a sculpt… Makes a nice render, but it won’t animate well. You need to do a retopo on his gear, to get decent meshes for his stuff.
OR!
Separate by Loose Parts. Then for each of his things(Shoulder pads, bandoleers, etc.) join them back into their own objects. Give the bandoleers a mesh deform, then animate that with the body. And the arm, leg, and head stuff just parent it to the bones. (I think that’ll work)
Here’s the harsh part!!! I separated him. I didn’t count them all but you’ve got what appears to be Mesh.0 through Mesh.1349 all simply joined together, then you want Blender to sort it out for you. You can’t build an animate-able model that way. Even if you’re doing something as crude as booleans it’s going to work better than just hanging 1,000 pieces in 3D space and doing Object->Join.
Here’s the harshest part… You gotta learn to model man! 
Keep it up. You’re on the right track, you just got a ways to go.
Playing with it a bit more… Go into edit mode and Select->Loose Verts/Edges… Delete that junk… WOW! That cut it down to 238 pieces. Might try doing the auto weights again…
EDIT: It parent OK but weights are messed up, and as I said before I think, with all those loose pieces it is going to be hell to paint weights on the model.
I’m just in the mood for animating! 
I’m not that great with modeling, which is why I’ve switched to the rigging and animation side. But I suppose this cleanup is good experience anyhow, don’t you think? 