As long as you're sure there's room between the toilet and the flange for the wax, you can shim the toilet. They make plastic shims that work well -- HD carries them for a couple bucks a pack. I'd place the toilet, shim to level it, and tape the shims to the floor so they don't move. Then remove and replace the toilet, with the wax ring in place, back down on the shims. Snap off the portion of the shims protruding from under the toilet. (You can also cut the shims before placing the toilet if you'd rather, but the plastic shims snap pretty clean.) Caulk around the toilet, leaving a gap in the back (or not -- depends on local codes and your taste).