If you are going up in tire size, that will lower your RPMs with your current gears. I wouldn't swap to higher gears with 4" larger tires, that would drop the RPMs too much, IMO.
Are you sure your numbers are right? 110KMH is about 68MPH and in my calculator it says you should only be turning about 3100RPM at 68MPH with 30" tires. That is figuring you have a 5 speed tranny and the tires actually measure 30". If you have the auto, you are probably turning a little higher RPM than what I figured, but not 600RPM more. And the tires probably do not measure 30", but I still don't see there being that much of an RPM difference.
If your numbers are correct, then going to a 4" taller tire will drop the RPMs down to 3232 at 110KMH, if you keep the 5.12s. If you go to 4.62s, the RPMs will drop to 2917 at 110KMH.