Coarse-grained (CG) models provide a computationally efficient means to study biomolecular and other soft matter processes involving large numbers of atoms correlated over distance scales of many covalent bond lengths and long time scales. Variational methods based on information from simulations of finer-grained (e.g., all-atom) models, for example the multiscale coarse-graining (MS-CG) and relative entropy minimization methods, provide attractive tools for the systematic development of CG models. However, these methods have important drawbacks when used in the "ultra-coarse-grained" (UCG) regime, e.g., at a resolution level coarser or much coarser than one amino acid residue per effective CG particle in proteins. This is due to the possible existence of multiple metastable states "within" the CG sites for a given UCG model configuration. In this work, systematic variational UCG methods are presented that are specifically designed to CG entire protein domains and subdomains into single effective CG particles. This is accomplished by augmenting existing effective particle CG schemes to allow for discrete state transitions and configuration-dependent resolution. Additionally, certain conclusions of this work connect back to single-state force matching and open up new avenues for method development in that area. These results provide a formal statistical mechanical basis for UCG methods related to force matching and relative entropy CG methods and suggest practical algorithms for constructing optimal approximate UCG models from fine-grained simulation data.