However, I'm unclear what it means to attribute free will to G-d. Since, G-d does not, in fact, do everything, what could it mean for Him to be "able" to do so? Saying something like "It means that there's nothing He can't do" won't help, because there are, in fact, things He does not do.
I don't find this a problem for human's free will, and maybe if I explain why my question will be clearer. After considering the question of what exactly free will is, I ended up defining it in terms of predictability. That is, human Ploni has free will on a decision X, if it cannot be predicted in advance what decision will be made. So if it is known that someone won't do something, it's viewed as if they don't have free will. (Example, Lev Melachim B'yad Hashem, so Pharaoh didn't have free will at certain times).
That cannot apply to G-d, because there are things that we know He won't do (according to some Rishonim, anything that breaks the "teva", or not fulfilling promises that He made, etc.) So what precisely do we mean when we say that he can do anything. What does "He can do something" mean, if He does not do that thing? How can free will be defined so that it applies to G-d?
Edit: A source for the statement "G-d can do anything" is Iyov 42:2:
I know that Thou canst do every thing, and that no purpose can be withholden from Thee.
Some sources for "there are some things we know G-d won't do":
And I will establish My covenant with you; neither shall all flesh be cut off any more by the waters of the flood; neither shall there any more be a flood to destroy the earth.
Thus saith the LORD, Who giveth the sun for a light by day, and the ordinances of the moon and of the stars for a light by night, who stirreth up the sea, that the waves thereof roar, the LORD of hosts is His name. If these ordinances depart from before Me, saith the LORD, then the seed of Israel also shall cease from being a nation before Me for ever.
The first says that G-d won't destroy the earth with a flood, and the second says that G-d won't destroy Israel until the sun, moon and stars go out.
Edit: Another source can be found in Derech Hashem: (from translation)
No bounds or limits can be placed on God's Omnipotence, [and therefore, there is nothing preventing Him from creating even evil if He so desires].
So it implies that a limit on creating evil would be a "bound or limit". This seems to contradict the verses quoted earlier, which put restrictions on what Gd will do.