As for the wings bit...I think they had them, and used them, but they only flew when they had to. There's a part in
the Silmarillion that states that
Morgoth or
Glaurung or someone sent tongues of flame "faster than the
Balrogs" sweeping over Ard-Galen. And I think that wings would be the best way to move quickly over long distances (like the Balrogs coming to Morgoth's aid when
Shelob attacked him). There are probably other ways of
travel. Maybe Balrogs can fly without wings, but I've always saw them as having wings.