Is this a valid sentence structure, and what is it called?

Sprinkling liberally your writing with any pet structures tends to make it stilted and artificial. It spices up your writing to diversify structures and sometimes— take bold leaps to flout the rules (This, of course, hardly means that you could make or breaks rules at will.)

Now—

He stomped off, muttering to himself.

is a perfectly valid construction, where muttering to himself is the participle phrase acting as a modifier.

Of course, you could go with your other version (using while or as), and it depends on what and how you want your message to come through.

Significantly, the while version is probably just as good as the original here, but it's not always that you could use the two versions interchangeably: You could compromise the exactitude of your implied meaning. To illustrate with an example— [Pursued by bandits, he managed to get safely to his home]— it's unclear whether the two actions—pursued and managed to get safely to his home— are occuring simultaneously or not. Here the while version might do the trick.

So the bottom line is that it depends on what you want to convey and how you want to convey it. Rest, the English language does really offer you a cornucopia of choices to pick from.