Are there other ways to skin a mesh without Armature Deform with Automatic Weights?
You could parent the object to the armature with empty weights and then do the weights yourself. You might have better luck starting with a basic rig that is already linked into a shape and then match it up within your object and then try pairing it with automatic weights you might have better luck. Normally, it works, but there is always autorig pro, it has a smarter automatic weight painting system, you would probably like it.