Nonlinear device characteristics present a severe performance-bottleneck for several upcoming next-generation wireless communication systems and prevent them from delivering high data-rates to the end-users. In this context, reproducing kernel Hilbert space (RKHS) based signal processing methods have gained widespread deployment and have been found to outperform classical polynomial-filtering-based solutions significantly. Furthermore, recent RKHS based techniques that rely on explicit feature-maps called random Fourier features (RFF) have emerged. These techniques alleviate the dependence on learning a dictionary and avoid the computations and errors incurred in dictionary-based learning. However, the performance of existing RKHS based solutions depends on choosing a suitable kernel-width. For the widely-used Gaussian kernel, we propose a methodology of assigning kernel-bandwidths that capitalizes on a stochastic sampling of kernel-widths using an ensemble drawn from a pre-designed probability density function. The technique is found to deliver a comparable convergence/error-rate performance to the scenario when the kernel-width is chosen by brute-force trial and error for tuning it for best performance. The desirable properties of the proposed kernel-sampling technique are supported by analytical proofs and are further highlighted by computer-simulations presented in the form of case studies in the context of next-generation communication systems.