First of all, the assertion that "With God, all things are possible" is valid and scriptural.
Matthew 19:26 (NIV)
26 Jesus looked at them and said, “With man this is impossible, but with God all things are possible.”
However, it would be a mistake to assume that God's omnipotence means he can act against his nature. Hebrews tells us:
Hebrews 6:18 (NIV)
18 God did this so that, by two unchangeable things in which it is impossible for God to lie, we who have fled to take hold of the hope set before us may be greatly encouraged.
This is not a contradiction. When Jesus says that "with God all things are possible", he does not intend to suggest that God can act outside of His nature - and His nature is righteousness. Similarly I, as a physical creature, am by nature bound to operate within the confines of a physical universe (i.e., I am bound by physical laws).
As to the other part of your question, no - God cannot make a rock so big that he can't lift it. That doesn't contradict His omnipotence. The question itself is silly and irrational. Another thing God can't do is make a circle with four corners. If he did, then it would no longer be a circle would it? By definition, it would be a square. C.S. Lewis addresses this eloquently:
His Omnipotence means power to do all that is intrinsically possible, not to do the intrinsically impossible. You may attribute miracles to Him, but not nonsense. There is no limit to His power.
If you choose to say, 'God can give a creature free will and at the same time withhold free will from it,' you have not succeeded in saying anything about God: meaningless combinations of words do not suddenly acquire meaning simply because we prefix to them the two other words, 'God can.'