The strange dark-backed gull has been present both days, however. As noted before it has too much dark on the nape to be a greater black-backed. The face looks too triangular to my eyes as well. While Greater Black-backeds don't usually give me quite as great the heavy jawed appearance of a Glaucous Gull, they have more than this bird. In bright sun its legs look yellowish, though in the overcast of yesterday and today they are the more grayish-pinkish which would be more consistent with the offspring of two pink-legged birds.
Here's the bird quartering away showing the heavy gonydeal angle which too my eyes is way too much for Lesser Black-backed (see here for lots of Virginia Beach Lessers):
Here the bird is more distantly yesterday. The size impression from this photo is a little misleading as the bird in question is the farthest away down the beach. You'll have to take my word (or look at Tim's pics) that it is slightly bigger than the Herring Gulls. It does give somewhat of a comparison of the shade of gray between it and the adult Greater more on the left side of the frame. The birds aren't in exactly the same pose, which can lead to artifact, but I think that the picture was fairly true to life in what it portrays in this respect as it was only a shade lighter than the Greater.
Olsen and Larssen gives Greater Black-backed a Kodak shade of 11-13, and graellsii Lesser Black-backed a Kodak shade of 8-10. Interestingly Slaty-backed is 11-12 so this is about the shade that it would probably appear (Slaty-backed is easily ruled out based on lacking a lot of dark marking about the eye, not really being pot-bellied, not having bright pink legs, and obviously the wrong primary pattern). Based on the traditional pitfall of Lesser Black-backed x Herring Gull hybrids approaching the mantle color of Yellow-legged Gull and the intermediate results observed in the Chandeleur Kelp x Herring Louisiana hybrid "experiment" (read here for an excellent article suggested by Caleb), this is probably not an F1 hybrid, and most likely some flavor of back-cross given how dark the mantle is. Here's a webpage describing a possible GBBGxHEGU from Massachusetts that eventually became a specimen; it does have a mantle that's paler than our bird (though as noted by the authors some suggestion of pearls in the primaries). Here's a note from the Auk from the 1970's describing a presumed Greater Black-back x Herring shot in the Niagara area; it too had a paler mantle than our bird.