I might be missing something big, but isn't chemical equation balancing just a system of linear Diophantine equations[1]? If it is, you should be able to solve it in O(n^3) time by converting to Smith normal form[2]. Unlike Hermite form, which the paper mentions, you don't need rational arithmetic or floating points.
Yeah, I remember using gaussian elimination to solve them in high school chemistry. My teacher taught us some guess and check method when it was clearly just a system of linear equations. He gave us a "challenge" problem with more variables than normal; much to his chagrin, I popped it into my TI-89 and had a solution within a few minutes.
[1]https://en.wikipedia.org/wiki/Diophantine_equation#System_of... [2]https://en.wikipedia.org/wiki/Smith_normal_form