This talk is centered around two new efficient techniques that can be used to approximate (Tikhonov-like-)regularized solutions to large scale linear inverse problems, with an outlook on how such methods can be employed in a Bayesian setting. First, we propose a randomized Golub-Kahan approach that builds on the recently developed randomized Gram-Schmidt process, where sketched inner products are used to estimate inner products of high-dimensional vectors. We describe new iterative solvers based on the randomized Golub-Kahan approach and show how they can be used for solving inverse problems with rectangular matrices, thus extending the capabilities of the recently proposed randomized GMRES method. We also consider hybrid projection methods that combine iterative projection methods, based on both the randomized Arnoldi and randomized Golub-Kahan factorizations, with Tikhonov regularization, where regularization parameters can be selected automatically during the iterative process. Second, we consider the well-established FLSQR and FLSMR methods (i.e., flexible variants of LSQR and LSMR, respectively), which naturally allow modifications of the solution approximation subspace and/or handling inexact matrix-vector multiplications with the (transpose of the) coefficient matrix. We introduce sketched variants of FLSQR and FLSMR, where randomization becomes particularly effective, as it allows to recover short recurrences for the solution approximation. Theoretical results are provided, and the performance of the new randomized Krylov methods is validated through numerical results in image deblurring, low-rank regularization and tomography with and without unmatched backprojectors.