A central challenge for many quantum technologies concerns the generation of large entangled states of individually addressable quantum memories. Here, we show that percolation theory allows the rapid production of arbitrarily large graph states by heralded photonic entanglement in a lattice of atomic memories. This approach can greatly reduce the time required to produce large cluster resource states for quantum information processing, including states required for universal one-way quantum computing. This reduction puts our architecture in an operational regime where demonstrated collection, coupling and detection efficiencies are sufficient for generating resource states for universal quantum computing within an experimentally demonstrated coherence time. The approach also dispenses the need for time consuming feed-forward, high-cooperativity interfaces and ancilla single photons, and can also tolerate a high rate of site imperfections. We also derive the minimum coherence time for the atomic memory to scalably create large-scale photonic-entanglement without feed-forward as a function of collection efficiency, setting a critical benchmark for future experimental demonstrations. We also propose a variant of the architecture with long-range connections that makes our architecture even more resilient to low site yields. We analyze our architecture for nitrogen-vacancy (NV) centers in diamond, though the approach applies to any atomic or atom-like system.