Just build a non deterministic AI. Free will and true AI are not (necessarily) mutually exclusive.

"Free will" is a vague concept anyway. What does it really mean to make a decision? It already is heavily weighted by your knowledge and experience, everything else would be "random".

A smart (smarter than us) machine shouldn't have "free will" anyway, as all choices should be exhaustively evaluated for their pros and cons.