Kipster you generally don't have to change shifter only rear derailleur. What setup do you have? Rear derailleur are cheap enough, and with a cass being cheap aswell 11-32 or 11-34 11-36 are possible. other option is a mtb crankset 38/26 36/22 depending on bottom bracket. I did fit a 36/22 Shimano slx crank and a 11-36 cass to my wifes shopper bike which had a road size bottom bracket. It works a treat and allows her to climb silly hills and she is not a dedicated rider.
My personal setup involves a custom hanger and 11-40XT cass, married to Shimano 50/34 crank on my CXR
Hills then become no problem at all, you just spin up at a comfortable pace