[Warning: what follows is a bit intricate. I suspect it can be streamlined.]
To determine whether a configuration is solvable,
first place an extra two heads on each end. Then note for each head how many tails are to its left and compute the sum of (-1)^(# tails to the left) over all heads mod 3. (That is: +1 when the number of tails to the left is even, -1 when it's odd.) If the result is a multiple of 3 then the configuration is not solvable; otherwise, it is. There is just one (obvious) exception: if the configuration consists of a bunch of tails and no heads at all, it is not solvable even though (if the number of tails is even) the number you obtain is 4.
Proof:
First, let's see what happens to this "score" when we make a move. Suppose first of all that the head we remove is not at either end of the row. We replace p H q with p' q' (I trust the notation is obvious). Since p,q have both flipped and the coin we removed was H, the signs of the stuff to the right have not changed. There are four possibilities, and we might as well just check them all: T H T (-1) -> H H (2); T H H (-2) -> H T (1); H H T (2) -> T H (-1); H H H (3) -> T T (0). In all cases, the sum mod 3 is unaltered. What if the head we remove is at one end? At the left end we have [H H] H H -> [H H] T or [H H] H T -> [H H] H; writing s for the "tail score" we are replacing 4+s with 2-s or 3-s with 3+s, and while this can change the score mod 3 neither operation can change whether the score is a multiple of 3. And at the right end we have H H [H H] (4) -> T [H H] (-2) or T H [H H] (-3) -> H [H H] (3) and the score doesn't change mod 3. Oh, one more case: if our head is at both ends then the configuration is [H H] H [H H] which reduces to [H H] [H H]; and neither 5 nor 4 is a multiple of 3. So -- and I suspect there was a neater way to prove this -- no legal move makes a difference to whether the score is a multiple of 3.
Now
if we manage to empty the row, all that remain are the two "dummy" heads we added on each end, and H H H H has a score of 4, which is not a multiple of 3. This establishes that if the initial score is a multiple of 3, then we can't remove all the coins. So, a fortiori, if the initial score is a multiple of 3 or the initial position has tails but no heads, then we can't remove all the coins.
And
if the initial score is not a multiple of 3 and the initial position contains at least one head, then let us make whatever moves we like except that we will not allow ourselves to make a move that leaves no heads unless it also leaves no coins. Clearly if we can keep doing this then we will eventually have no coins -- so can we do it? Well, let us adopt the following rule: we will always find a block of heads and remove the coin at one end of the block, and we will pick the end that's furthest from the end of the row. (In the event of a tie, choose either.) If this move leaves no heads then the coin we removed must actually have been at an end of the row (else there would have been a T next to it, which would have become H); so (since we pick the further-from-the-end end of a block) in fact our whole row must have been a single block of H. And since removing one end of it left no heads, it must have had length <= 2. And since it didn't remove all the coins, it must have had length >= 2. So its length was exactly 2, so our augmented row was [H H] H H [H H], with a score of 6, which is a multiple of 3. This establishes (since if the score is ever a multiple of 3 then it's always a multiple of 3) that if we can't remove all the coins then either the initial score is a multiple of 3, or the initial position had no heads.
This completes the proof; and the last spoilered paragraph above happens to include an algorithm that does the job. (The bit in boldface.)
