We present a classical algorithm based on Pauli propagation for estimating expectation values of arbitrary observables on random unstructured quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that for any architecture where each circuit layer is randomly sampled from a distribution invariant under single-qubit rotations, our algorithm achieves a small error (\epsilon) on all circuits except for a small fraction (\delta). The computational time is polynomial in qubit count and circuit depth for any small constant (\epsilon, \delta), and quasi-polynomial for inverse-polynomially small (\epsilon, \delta). Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries. We further conduct numerical experiments beyond our average-case assumptions, demonstrating the potential utility of Pauli propagation methods for simulating real-time dynamics and finding low-energy states of physical Hamiltonians.