A major challenge for primordial neutral hydrogen (HI) cosmology is to extract a signal that is about 104-6 times smaller than the low radio frequency foreground, with unmeasured, large solid-angle, chromatic beams introducing spectral distortions. Using our novel pattern recognition methodology, we completed a data analysis pipeline to self-consistently separate the sky-averaged 21-cm signal from the large beam-weighted foreground. In the first paper of the pipeline series, we showed how to obtain optimal basis vectors from signal and beam-weighted foreground training sets (based on HI theory, beam simulations and foreground maps) to linearly fit both components simultaneously with the minimal number of terms that best extracts the signal given its overlap with the foreground. In the second paper of this series, we utilize the spectral constraints derived in the first paper to calculate the full posterior probability distribution of any nonlinear signal model of interest. This spectral fit provides the starting point for a Markov Chain Monte Carlo (MCMC) algorithm to sample the signal without traversing the foreground parameter space. At each step of the nonlinear MCMC calculation, we marginalize over the weights of all linear foreground modes and suppress those with unimportant variations by applying priors gleaned from the foreground training set. Conveniently, the application of foreground priors circumvents the need for selecting a minimal number of foreground modes. Also, the analytical marginalization over the foreground terms drastically reduces the number of required MCMC parameters, and therefore augments the efficiency of the MCMC exploration. In turn, this allows the complexity of the foreground model to be greatly increased with negligible computational time costs. Using two nonlinear signal models, we demonstrate the success of the pipeline by recovering the input parameters from several randomly simulated signals at low radio frequencies (10-200 MHz), while rigorously accounting for realistically modeled beam-weighted foregrounds. This pipeline is designed in particular for NASA’s Dark Ages Polarimeter Pathfinder mission concept, and its ground-based prototype, the Cosmic Twilight Polarimeter.