There are other ways to 'map' the structure of a mesh to the underlying skeleton but none of them are entirely trouble-free, especially so when achieved via automated processes, offer the control you really need, or are compatible for game engine tech - from that point of view 'bones' are the most efficient way to animate a structure.
What you might want to try doing is blocking out a broad group of vertices first, so bones that don't have a left/right pairing - "spine", "head" and so on - get first treatment you can then go over the mesh doing both sides sequentially; rather than going down the left side and then switching to the right side, a better way to do it might be flipping side-to-side - left-shoulder > right-shoulder, left-arm, right-arm and so on, that way you can use the same 'paint value' on both bones are you weight them (I've never been too fond of the axis flip and duplication modifier myself, so will rig manually as outlined above).
Re the hair: If it's 'on fire' why not make a show of that as an effect, a sort of "here's a neat trick to try" type of affair with animated textures (flaming hair) and particle effect? Could/can you add physics to that so the flames flop about when she moves? The effect could be expanded on from there.. changes colour when she gets angry, dims and goes out when she's killed and so on. So many possibilities, tangent subjects/things to try ahoy!!