Experimental evidence collected over the years shows that blood exhibits non-Newtonian characteristics such as shear-thinning, viscoelasticity, yield stress and thixotropic behaviour. Under certain conditions these characteristics become relevant and must be taken into consideration when modelling blood flow. In this work we deal with incompressible generalized Newtonian fluids, that account for the non-constant viscosity of blood, and present a new numerical method to handle fluid-rigid body interaction problems. The work is motivated by the investigation of interaction problems occurring in the human cardiovascular system, where the rigid bodies may be blood particles, clots, valves or any structure that we may assume to move rigidly. This method is based on a variational formulation of the fully coupled problem in the whole fluid/solid domain, in which constraints are introduced to enforce the rigid motion of the body and the equilibria of forces and stresses at the interface. The main feature of the method consists in introducing a penalty parameter that relaxes the constraints and allows for the solution of an associated unconstrained problem. The convergence of the solution of the relaxed problem is established and some numerical simulations are performed using common benchmarks for this type of problems.