Well, it's not just governments that take land by violence. I'd like to be surprised by how few people have made any serious effort to answer the actual questions in the OP, but of course I am not.
Well, in all fairness, you asked your questions wrong -- your presentation presumed a fact not in evidence. But if you wish we can set that aside...
Does a military victory, alone, constitute a legal means of acquiring new territories? If so, on what moral or legal basis?
From a Natural Law perspective, no, it doesn't. If you hold to a different Philosophy of Law, tell us which PoL you have in mind.
Does the conquering "army" have to have the official imprimatur of their government in order for an invasion to be legal,
"Legal" by the law of the invading country, yes, of course; but I think that's not what you're asking. Legal by the law of the invaded country, no, not as a rule; but the devil's in the details and you'd have to check the specific invaded country's laws. (The Partitions of Poland by Russia, Prussia and Austria were probably legal by Polish law, given that Poland's government legally could do jack squat without a unanimous vote.) Retroactively legal by the laws of the new regime (assuming the invasion succeeds), again, it depends. Typically it's retroactively legalized immediately; and then, generations later when there's no risk of the facts on the ground being reversed, it may be retroactively illegalized again and an empty apology may be issued.
or can random settlers acting unofficially be the basis of a new territorial acquisition?
Well, now that we've disposed of right of conquest as a legal basis equally for granting title to the attackers or for letting the defenders retain title, that pretty much leaves us with only one passable legal basis for anyone to get title to disputed land: self-determination of the residents. Which is to say, yes: when enough random Albanians acting unofficially settle in Kosovo that ethnic Albanians can outvote the local preexisting Serb population, if they vote to make Kosovo an independent Albanian-majority country instead of a region of Serbia then they get to do that; and it's legal because Democracy. And if the Serb minority don't like it, I don't blame them; but sympathy doesn't magically turn "We were here first" into a substantive argument for letting a minority rule over a majority.
"We were here first" is a non-substantive argument for two reasons. First, because it isn't literally true. The Kosovars have been there exactly as long as the Kosovo Serbs: all their lives. The Kosovars aren't immigrants; they're mainly the native-born descendants of Albanians who immigrated in the 1700s and 1800s.
And second, for moral/Natural Law purposes it's non-substantive because although "We were here first" is
metaphorically true when Serbs metaphorically use "We" to mean "Not me, but different people I'm descended from", nonetheless, the argument amounts to "This is Serb land and not Kosovar land because Serbs inherited it from the rightful owners and Kosovars didn't." And that's a non-substantive argument, because it's exactly the same argument as "England is Queen Elizabeth's land because she inherited it from William the Bastard."