The locomotion of microswimmers in non-Newtonian fluids is of crucial importance in many biological processes including infection, fertilisation, and biofilm formation. The behaviour of flagellated swimmers in these media remains an area with many conflicting results, with cells displaying varying responses depending on their precise morphology, propulsive mechanisms, and elastic properties, as well as the complex characteristics of the fluid itself. We numerically investigate the effect of non-Newtonian properties, including shear-thinning rheology and viscoelasticity, on both planar sperm-like swimmers and helical bacterial locomotion. This is achieved through a novel hybrid computational approach that utilises known Newtonian solution techniques (The Method of Regularised Stokeslets [1]) to approximate the rapidly varying three-dimensional flow surrounding a swimmer, with a non-Newtonian correction term obtained through solving using the finite element method (FEM). Crucially, the FEM solver is formulated in such a way that the solution can be calculated on a coarse mesh, for decreased computational costs compared to more commonly used body-fitted meshes. For sperm-like swimmers, the inclusion of swimmer elasticity allows us to demonstrate that complex rheology can either enhance or hinder propulsion, depending on a balance of elastic and viscous forces within the problem. For rigid helical swimmers, we compare the effects of shear-thinning rheology and fluid elasticity on swimming speed and efficiency of cells, with the combination of both effects modelled using a Giesekus constitutive law [2]. Our results, through considering a variety of fluid and swimmer properties, are sought to bridge the gap between the conflicting experimental and theoretical observations in the literature. Additionally, we discuss the relevance of our findings to clinical sperm assessment, as well as the possible implications on the initial stages of bacterial biofilm formation. [1] R. Cortez. The method of regularized Stokeslets. SIAM, Vol. 23(4), pp.1204-1225, 2001. [2] H. Giesekus. A simple constitutive equation for polymer fluids based on the concept of deformation-dependent tensorial mobility. J. Non-Newton. Fluid Mech. Vol. 11(1-2), pp.69-109.