Typical fermion algorithms require the computation (or sampling) of the fermion determinant. We focus instead on cluster algorithms which do not involve the determinant and involve a more physically relevant sampling of the configuration space. We develop new cluster algorithms and design classes of models for fermions coupled to $\mathbb{Z}_2$ and $U(1)$ gauge fields that are amenable to being simulated by these cluster algorithms in a sign-problem free way. Such simulations should contain rich phase diagrams and are particularly relevant for quantum simulator experiments.