We develop a Monte Carlo scheme for sampling series of Feynman diagrams for the proper self-energy, which are self-consistently expressed in terms of renormalized particle propagators. This approach is used to solve the problem of a single spin-down fermion resonantly interacting with the Fermi gas of spin-up particles. Though the original series based on bare propagators are sign alternating and divergent, one can still determine the answer behind them by using two strategies (separately or together): (i) using proper series resummation techniques and (ii) introducing renormalized propagators which are defined in terms of the simulated proper self-energy, i.e., making the entire scheme self-consistent. Our solution is important for understanding the phase diagram and properties of the Bardeen-Cooper-Schrieffer–Bose-Einstein Condensation crossover in the strongly imbalanced regime. On the technical side, we develop a generic sign-problem tolerant method for exact numerical solution of polaron-type models and, possibly, of the interacting many-body Hamiltonians.