How to fill an area outside circles?

I guess a very easy way would be to use a scope then clip using the circles, and then invert the clip using Jake's reverseclip style.

Adding the backgrounds library, and then adding [on background layer] to the scope will make sure that our fill won't cover the other lines.

Output

^{Note: the magnification is not included in the code below, just to show the clipping up close.}

Code

\documentclass[tikz,margin=15pt]{standalone}
\usepackage{pgfplots}
\pgfplotsset{compat=1.10}
\usetikzlibrary{pgfplots.fillbetween, backgrounds}

\tikzset{
    reverseclip/.style={insert path={(current page.north east) --
        (current page.south east) --
        (current page.south west) --
        (current page.north west) --
        (current page.north east)}
    }
}

\begin{document}
\begin{tikzpicture}
\begin{axis}[
    width=6cm, height=6cm,
    xmin=-0.2, xmax=1.2,
    ymin=-0.2, ymax=1.2,
    xlabel = {$ x_1 $},ylabel = {$ x_2 $},
    xtick={0,0.167,0.33,0.5,0.66,0.833,1.0},
    xticklabels={$0$,$\frac{1}{6}$,$\frac{1}{3}$,$\frac{1}{2}$,$\frac{2}{3}$,$\frac{5}{6}$,$1$},
    ytick={0,0.167,0.33,0.5,0.66,0.833,1.0},
    yticklabels={$0$,$\frac{1}{6}$,$\frac{1}{3}$,$\frac{1}{2}$,$\frac{2}{3}$,$\frac{5}{6}$,$1$},
    every tick label/.append style={font=\scriptsize},
    enlargelimits=0.05,
]

% Draw rectangle
\addplot[draw,blue,very thick] coordinates { (0,0) (1,0) (1,1) (0,1) (0,0) };

% Draw sampling points
\addplot[only marks,mark=*,nodes near coords,point meta=explicit symbolic, color=blue, font=\scriptsize] coordinates {
    (1/3,1/3) [(1)]
    (2/3,2/3) [(2)]
};

% Draw diameter
\addplot[color=red] coordinates { (1/3,1/3) (0,0) } node[pos=0.5,yshift=8pt,sloped] { $\delta$};

% Draw circles
\draw[red,dashed] (axis cs:0.33,0.33) circle[radius=0.471];
\draw[red,dashed] (axis cs:0.66,0.66) circle[radius=0.471];

\begin{scope}[on background layer]
\clip (axis cs:0.33,0.33) circle[radius=0.471] [reverseclip];
\clip (axis cs:0.66,0.66) circle[radius=0.471] [reverseclip];
\fill[green] (axis cs:0,0) rectangle (axis cs:1,1);
\end{scope}
\end{axis}
\end{tikzpicture}
\end{document}