The breakdown of the lattice Kondo effect in local-moment metals can lead to nontrivial forms of quantum criticality and a variety of non-Fermi-liquid phases. Given indications that Kondo breakdown transitions involve criticality not only in the spin but also in the charge sector, we investigate the interplay of Kondo breakdown and strong valence fluctuations in generalized Anderson lattice models. We employ a parton mean-field theory to describe the transitions between deconfined fractionalized Fermi liquids and various confined phases. We find that rapid valence changes near Kondo breakdown can render the quantum transition first order. This leads to phase-separation tendencies which, upon inclusion of longer-range Coulomb interactions, will produce intrinsically inhomogeneous states near Kondo breakdown transitions. We connect our findings to unsolved aspects of experimental data.