To kill two birds with one stone is to solve two problems at once.
You might also consider saying that the solution does both things in one fell swoop (at one time or with one action), though this is not limited to accomplishing only two things.
Keep in mind that to be the best of both worlds typically connotes not necessarily solving two problems, but combining two things that normally don't go together. Consider examples like, "it's the best of both worlds because we have the feel of a small college but the resources of a large university". In such cases, it's often a stretch to imagine how something can really have both of these benefits (is it truly a floor wax and a dessert topping?) which probably contributes to your feeling that the idiom is cliché.
If your desire is to avoid the overused, you might choose a simple variant of your original language, perhaps emphasizing that both problems are solved at once: Not only does this solve X, but it simultaneously solves Y.