We investigate the interplay of many-body and band-structure effects of interacting Weyl semimetals (WSMs). Attractive and repulsive Hubbard interactions are studied within a model for a time-reversal-breaking WSM with tetragonal symmetry, where we can approach the limit of weakly coupled planes and coupled chains by varying the hopping amplitudes. Using a slab geometry, we employ the variational cluster approach to describe the evolution of WSM Fermi arc surface states as a function of interaction strength. We find spin and charge density wave instabilities which can gap out Weyl nodes. We identify scenarios where the bulk Weyl nodes are gapped while the Fermi arcs still persist, hence realizing a quantum anomalous Hall state.