It is rare, but does occur. The with phrase is a prepositional phrase containing a verbless clause (subject + predicate, but with no verb).
The Oxford Dictionary of English Grammar p4 defines an absolute clause as:
A non-finite or verbless clause containing its own subject,
attached to a sentence from which it is separated by a comma (or
commas), and not introduced by a subordinator. Also called absolute
construction.
However, in this case, the clause is a dependent of with, which would put it outside this definition.
The Cambridge Grammar of the English Language p1267
Complement to with and without
iThey were standing against the wall [with their hands above their
head].
ii They were wandering around [without any clothes on].
iii [With the children so sick], we weren’t able to get much
work done.
iv Who is that guy [with his hands in his pockets]?
The [bolded] clauses have subject + predicate structure, but with no
verb in the predicate. With and without do not license finite
complements, but non-finites are found in addition to the verbless
forms. The bracketed PPs function as adjunct to a clause ([i—iii]) or
post-modifier in NP structure ([iv]). With is semantically similar
to have, and without to not have: [i—ii], for example, entail
They had their hands above their heads, They didn’t have any clothes on.
In the example provided, the function of the with... phrase would be an adjunct of reason, telling us why it is no surprise that....
Though the above references do not have noun phrases as both the subject and the predicate in the verbless construction, there examples of similar to be found:
[With bicycles the best way to get around and no mobile phone
reception], there's plenty of time to relax and attune yourself to the
idyllic surroundings. (Australia Highlights - AKDMC)
[With Jake the only occupant], the suite is quiet compared to the hustle
and bustle of the thirty-eight-lawyer space I shared in downtown
Manhattan near the South Street Seaport. (One man's paradise;
Corleone, Douglas; Minotaur Books 2010)
[With family the only social security network], if a couple has no sons,
they will starve to death in their old age.
(http://www.dailykos.com/story/2012/10/10/1142939/-Never-loved-Lawrence-O-Donnell-as-much-as-today)
[With himself the sole loser by possible mistakes of judgment],
Washington did not have to display the public "care and caution" that
had been the vigilant law of his anxious life in the Army.
(Washington's Hardest Decision; Douglas Southall Freeman; Atlantic
Monthly: 1952:)
[With Ethan the sole survivor], the CIA believed he was the mole.
(http://www.superherodb.com/ethan-hunt/10-10476/history/)
More commonly, being or as is inserted between the two NPs, but the usage without them does not strike me as ungrammatical.