Does this sentence of Melville lack a verb?

I agree broadly with Anton, but will suggest that the sentence in question is elliptical. Melville is saying that the officers' attitude on deck is certainly not the strangest thing - No! the strangest thing is their inoffensive, not to say deprecatory and humble air towards him at dinner. The quote says:

It is not the least among the strange things bred by the intense artificialness of sea-usages, that while in the open air of the deck some officers will, upon provocation, bear themselves boldly and defyingly enough towards their commander; yet, ten to one, let those very officers the next moment go down to their customary dinner in that same commander’s cabin, and straightway [the observer will see that] the most strange thing is their inoffensive, not to say deprecatory and humble air towards him, as he sits at the head of the table; this is marvellous, sometimes most comical.

No, "their" is used quite correctly here, as a possessive. It simply modifies "air". To simplify the phrasing by removing some words, it basically says:

Their inoffensive... air towards him... is marvellous.

The thrust of the passage seems to be that the attitude ("air") of naval officers towards their commander may be defiant in public view, and perhaps when that commander is not present to take offense. But those same officers are more conciliatory in a private setting when that commander is present.

I'm essentially agreeing with Edwin Ashworth's paraphrase, but I'll offer a second possibility as well; and I'll disagree with Anton's suggested paraphrase. First, here's the original paragraph again:

It is not the least among the strange things bred by the intense artificialness of sea-usages, that while in the open air of the deck some officers will, upon provocation, bear themselves boldly and defyingly enough towards their commander; yet, ten to one, let those very officers the next moment go down to their customary dinner in that same commander’s cabin, and straightway their inoffensive, not to say deprecatory and humble air towards him, as he sits at the head of the table; this is marvellous, sometimes most comical.

I've checked this against a couple of Google Books results and believe the punctuation is accurate. Melville's punctuation does not match how I would punctuate it. In particular I'd have to remove the comma after "sea-usages" and insert one after "humble":

It is not the least among the strange things bred by the intense artificialness of sea-usages that while in the open air of the deck some officers will, upon provocation, bear themselves boldly and defyingly enough towards their commander; yet, ten to one, let those very officers the next moment go down to their customary dinner in that same commander’s cabin and, straightway, their inoffensive, not to say deprecatory and humble, air towards him, as he sits at the head of the table; this is marvellous, sometimes most comical.

The punctuation above reflects Edwin Ashworth's paraphrase:

It is [strange] that while [on deck] some officers will, upon provocation, bear themselves boldly; yet let those very officers the next moment go down to (1) their customary dinner and (2) their inoffensive air towards him; this is marvellous.

The "go down to dinner and their inoffensive air" construction would be an example of zeugma (more or less). However, I admit that I'm troubled by the word "let" there. The paraphrase would work a heck of a lot better if that word "let" were deleted.

Anton suggested this paraphrase:

It is [strange] that while [on deck] some officers will, upon provocation, bear themselves boldly; yet let those very officers the next moment go down to their customary dinner and, straightway, their inoffensive air towards him [becomes apparent]; this is marvellous.

I disagree with this paraphrase, because I agree with Anton that it is "perhaps too short, and even ungrammatical." Yes, it is ungrammatical to leave off the verb "[becomes apparent]" in that way. I don't think it was any less ungrammatical in Melville's time.

I suggest this third paraphrase:

It is [strange] that while [on deck] some officers will, upon provocation, bear themselves boldly; yet let those very officers the next moment go down to their customary dinner and straightway their inoffensive air towards him is marvellous.

That is, if you assume that the final semicolon should be a dash —

It is not the least among the strange things bred by the intense artificialness of sea-usages that while in the open air of the deck some officers will, upon provocation, bear themselves boldly and defyingly enough towards their commander; yet, ten to one, let those very officers the next moment go down to their customary dinner in that same commander’s cabin, and straightway their inoffensive, not to say deprecatory and humble air towards him, as he sits at the head of the table — this is marvellous, sometimes most comical.

I'm quite sure there's a name for this rhetorical device of rewriting "That car is red" into a jumpy sort of "That car — it is red." It's not quite as broad as parataxis; but it's not coming to mind right now.

Anyway, I think that's the best paraphrase: "their air, it is comical." This reading isn't quite grammatical, but it is at least precedented. The subtle shades of connotative difference between semicolon (or colon) and dash are fairly recent traditions, I think.

'Their' is a possessive pronoun, i.e., a reference indicating possession of something belonging to either a person or object. In the passage, "their" refers to the officers going down to dinner, specifically, "their offensive... air", i.e., the attitude they possessed towards their (again!) commander. The usage is entirely normal, appropriate and correct.

When I can't tell at a glance if the grammar is correct in a complex or messy piece of writing, one thing I try is rewriting it with the adjectives and adverbs removed from it, and taking out some of the short phrases that modify or adjust but don't change the main idea of a sentence. For example, I'd rewrite the example as:

It is not the least among the things bred by the artificialness of sea-usages, that while in the open air of the deck some officers will bear themselves towards their commander; yet, ten to one, let those officers the next moment go down to their dinner in that commander’s cabin, and straightway their ... air towards him, as he sits at the table; this is marvellous.

I took out "upon provocation" and "the head of" and snipped words out of the part in question. It's clear now that "their" is the correct word.