The folks at Sneakybags have tackled this problem and come up with some solutions that are used by the kind of people for whom the term "denied area" is more than just a term. (Living in Massachusetts, I often feel like I'm in a denied area.) If we need both our weapons and grayness - either off- or on-duty - a several of their products are just the trick. Their Covert Rifle Bag is long enough to carry a fully functional AR-15 (or other long gun), but with its radiused corners, circular outside pocket, criss-crossed bungees and daisy-chain loops, it looks more like a short snowboard case than anything carrying a weapon. It "blends" in a coffee shop in Boston, in the seat of a pickup in New Mexico, or in a suburban mall parking lot. In all of its available colors, it's truly gray. Put a sweatshirt from your local university (with the logo showing) under the bungee lacing and you can disappear into the background. The case is moderately padded with protection on the bottom to hold up against sharp muzzle brakes. The interior is smooth so that nothing catches when you insert or withdraw your weapon. A 2-inch web strap (with padded sleeve) attaches to 2 of 8 D-rings for selectable slung carry. The 14-inch circular outside pocket is large enough to stash a lot of supporting gear, and will hold a stocked Mini-Sneaky shoulder bag (described below). There's also a flat Velcro-sealed pocket exterior pocket running from the bag's top to the circular pocket, and a small zippered pocket at the very top. You can definitely carry a lot in this bag... all the while remaining "gray". It comes in 31-, 37- and 43-inch lengths and in several colors.
My somewhat loaded-out AR-15 slid slickly in and out of this solidly-built bag, as did my Mossberg 590. Slung over a shoulder with the heavy guns in them, the bag distributed the weight well and was easy to carry. The oversize zippers made for sure and snag-free opening. Overall, this bag does a splendid job of carrying, providing access to, as well as disguising your long gun.
The Mini-Sneaky Bag is a single-flap bag made with the same over built features as the Covert Rifle Bag. It, too, has a 2-inch web shoulder strap with padded sleeve. Under the buckle-closed flap are three pockets. The main compartment, measuring 3.5 x 8.5 x 10-inches, is loop Velcro-lined to accept hook Velcro-backed pouch modules from Sneakybags (or other manufacturers) and has a drain hole in the bottom. The middle compartment is a draw-corded pocket measuring 8 x 2.5 x 8-inches. The outer bellowed pocket is flap covered and Velcro closed, and measures 5.5 x 7.5-inches. There's an 8 x 9-inch rear Velcro-closed document pocket and 2 x 3 arrays of PALS-like webbing on either exterior side of the bag, which looks more sporty than tactical. This bag doesn't look like a man-purse, but rather like a small messenger bag, and it definitely doesn't scream "tactical". The camouflage can be completed with an appropriate patch sewn on the flap. It's made to carry tactical gear (mags, med kits, spent mags, NV monocular, door wedges, cyalume sticks, construction crayons, tools, knife, etc.) and to support a tactical mission, not to carry everyday stuff (but if that's your need, the folks at Sneakybags are always in the lab, so stay tuned). It also features both a removable leg strap and a removable waist strap to secure the bag during tactical activities.
The Mini-Sneaky, even loaded out with mags, lights, med kit, etc., fits snugly into the circular pocket of the Covert Bag, and makes a great way to carry the extra gear you need when you need your rifle. Pulled out of there and slung over a shoulder, the waist and leg straps quickly buckle in, making the bag is secure and ready to go.
The SB-02 is another flap-covered, buckle-closed bag, but this time the size of a medium-sized messenger bag, and with the same shoulder, waist and leg straps as the Mini. Under the flap you'll find two compartments. The main one measures 10 x 10 x 4-inches and also is loop Velcro-lined. The outer one is draw-corded and measures 10 x 10 x 9-inches. The SB-02 also has a rear Velcro-closed document pocket of 11 x 9-inches. There are also 4 x 3.5 x 8.5-inch buckle-closed pockets on the exterior side of the bag, with drain holes. The SB-02 is internally stiffened with plastic panels to discourage the bag from collapsing, which shows some real thought and real-world feedback. This bag holds a lot of tactical gear, obviously, but because the side pockets are accessible without opening the main flap, it can be set up to carry both weapons/gear and your everyday gear. Also, the rear document pocket in both the SB-02 and the Mini will carry a small gun like a J-frame or Kel-Tec.
The SB-02 will carry a full load-out of gear for almost any tactical occasion, and the padded shoulder strap makes it quite comfortable to carry. You can fit almost as much in it as you can in a modular tactical vest, and with appropriate Velcro modules it's a well organized. The leg strap, in particular, makes it practical-it's hard to see how a shoulder bag without one could be used in a dynamic situation.
All three Sneakybags described here (they make other products, too) have a seriously over-built feel to them: heavy materials, strong stitching, wide webbing, robust buckles and Velcro (which comes in various strengths). They are structured and don't fold over on themselves or collapse when not fully loaded, and they support the weight of the loaded mags and pistols well. They are also American made. For no-key carry of weapons and associated gear, they are the ticket.