I took a look at your Model. Honestly, there should be a lot of cleanup done before you start rigging...
1) The different parts are one sided and open at various places. They should either be closed objects or connected to each other in a way that doesn't leave holes to avoid problems later in rendering.
2) Your UV's are extremely unclean, they overlap, the skin parts are just a flat frontal projection, etc etc etc... This could eventually be what creates the irratic behaviour of your skinweights. And if it doesn't, it will prohibit you from exporting/importing skinweights. clean UV's are quite important for rigging to go smoothly.
3) as @Baboonian already said. Your polycount is way to high for the amount of detail in your model. There are tons of unneeded vertices that only make rigging harder, slow down the rig and give more room for miscalculations, like the ones you are experiencing, to occur.
As I said in my first answer, if you want to handle a mesh like this in skinning, you need to work extremely careful. You should use an Addative workflow. Make use of selection based flooding. And make use of locking/unlocking joints in the paint skinweights tool.
But if you plan to go into rendering with this project later, you should clean up the mesh first, because something like this can be rigged, it can't be properly rendered. For example you won't have the ability to use SSS and you won't be able to apply complex textures.
