From the preview-latex documentation :
preview-LaTeX-command
When you generate previews on a buffer or a region, the command in preview-LaTeX-command gets run (that variable should only be changed with Customize since its structure is somewhat peculiar, though expressive). As usual with AUCTeX, you can continue working while this is going on. It is not a good idea to change the file until after preview-latex has established where to place the previews which it can only do after the LaTeX run completes. This run produces a host of pseudo-error messages that get parsed by preview-latex at the end of the LaTeX run and give it the necessary information about where in the source file the LaTeX code for the various previews is located exactly. The parsing takes a moment and will render Emacs busy.
Browse the AUCTeX customize-group to >Preview > Preview Latex and find the option Preview latex command.
Unfolded, it looks this way :

Replacing the line
%`%l "\nonstopmode\nofiles\PassOptionsToPackage{
with
%`%l -shell-escape "\nonstopmode\nofiles\PassOptionsToPackage{
should do the trick. Don't forget to click "Set for current session", and "Save for future sessions" if it works!