IMHO, the best solution would be to reduce the individual bonuses of the weapon skill and add element-specific damage bonuses based on the skills you have.
To be more specific: Have the weapon skills affect ONLY the base physical damage of a weapon, NOT the overall damage. Then have any other relevant skills, like the mage skills and the tenebrium skill apply damage boosting to any elemental damage that weapon does.
Redoing the actual % damage boosting is a matter of balancing.
To be fair, this isn't even my idea, I remember someone suggesting something similar to this, and I thought it was a good idea. It keeps the complexity of choice, with the right % damage added from skills, it keeps it balanced, and it makes nothing redundant.
