Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d) shows that for convex $A$ and $x\notin A$, $$\nabla f(x) = f(x)^{-1}(x-P_A(x)),$$ where $f(x)=d(x,A)$ is your function and $P_A(x)$ is the projection of $x$ onto $A$ (i.e., the unique $x^*\in A$ achieving the $\inf$). This shows, in particular, that for $x\notin A$, $||\nabla f(x)||_2=1$.

The Lipschitz property follows from Borwein+Lewis Section 2.1 Exercise 8(c.iii), which shows that projection is a contraction.

The full book reference: Convex Analysis and Nonlinear Optimization, Borwein, Jonathan, Lewis, Adrian S. http://www.springer.com/us/book/9780387295701

Edit: I forgot to state the additional hypothesis that $A$ is closed.

Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d) shows that for convex $A$ and $x\notin A$, $$\nabla f(x) = f(x)^{-1}(x-P_A(x)),$$ where $f(x)=d(x,A)$ is your function and $P_A(x)$ is the projection of $x$ onto $A$ (i.e., the unique $x^*\in A$ achieving the $\inf$). This shows, in particular, that for $x\notin A$, $\|\nabla f(x)\|_2=1$.

The Lipschitz property follows from Borwein+Lewis Section 2.1 Exercise 8(c.iii), which shows that projection is a contraction.

The full book reference: Convex Analysis and Nonlinear Optimization, Borwein, Jonathan, Lewis, Adrian S. http://www.springer.com/us/book/9780387295701

Edit: I forgot to state the additional hypothesis that $A$ is closed.

Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d) shows that for convex $A$ and $x\notin A$, $$\nabla f(x) = f(x)^{-1}(x-P_A(x)),$$ where $f(x)=d(x,A)$ is your function and $P_A(x)$ is the projection of $x$ onto $A$ (i.e., the unique $x^*\in A$ achieving the $\inf$). This shows, in particular, that for $x\notin A$, $||\nabla f(x)||_2=1$.

The Lipschitz property follows from Borwein+Lewis Section 2.1 Exercise 8(c.iii), which shows that projection is a contraction.

The full book reference: Convex Analysis and Nonlinear Optimization, Borwein, Jonathan, Lewis, Adrian S. http://www.springer.com/us/book/9780387295701

Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d) shows that for convex $A$ and $x\notin A$, $$\nabla f(x) = f(x)^{-1}(x-P_A(x)),$$ where $f(x)=d(x,A)$ is your function and $P_A(x)$ is the projection of $x$ onto $A$ (i.e., the unique $x^*\in A$ achieving the $\inf$). This shows, in particular, that for $x\notin A$, $||\nabla f(x)||_2=1$.

The Lipschitz property follows from Borwein+Lewis Section 2.1 Exercise 8(c.iii), which shows that projection is a contraction.

The full book reference: Convex Analysis and Nonlinear Optimization, Borwein, Jonathan, Lewis, Adrian S. http://www.springer.com/us/book/9780387295701

Edit: I forgot to state the additional hypothesis that $A$ is closed.