Is aspirin a possibility? Yes it's a blood thinner, and can trigger gut issues, but it IS an effective painkiller. Not very fashionable atm though.
Paracetamol scares me - the gap between an effective dose and a dose that kills your kidneys is quite small.