Spatio-temporal image fusion aims to increase the frequency and resolution of multispectral satellite sensor images in a cost-effective manner. However, practical constraints on input data requirements and computational cost prevent a wider adoption of these methods in real case-studies. We propose an ensemble of strategies to eliminate the need for cloud-free matching pairs of satellite sensor images. The new methodology called Unpaired Spatio-Temporal Fusion of Image Patches (USTFIP) is tested in situations where classical requirements are progressively difficult to meet. Overall, the study shows that USTFIP reduces the root mean square error by 2-to-13% relative to the state-of-the-art Fit-FC fusion method, due to an efficient use of the available information. Implementation of USTFIP through parallel computing saves up to 40% of the computational time required for Fit-FC.