We utilize a notion of "combinatorial gauge symmetry", where the gauge symmetry involves not just local rotations of spins, but also permutations of spins. This allows the construction of exact gauge invariant Hamiltonians using just two-body interactions. Models constructed in this way include the toric code and any Abelian and Non-Abelian generalization. New models also emerge in this paradigm. An advantage of the exact symmetry: the topological energy gaps need not be limited to a perturbative regime, but could potentially persist for a wider range of parameters. Possible realizations are discussed using arrays of superconducting wires and Josephson junctions. Overall, this appears to be a promising new approach for constructing experimentally realizable topological matter (spin liquids), with potential applications for quantum computing. The use of the exact combinatorial gauge symmetry differentiates it from previous perturbative approaches.