Since $2S = ab \sin C$, we can write
$$\begin{aligned} a^2 + b^2 - 4S &= a^2 + b^2 - 2ab \sin C = a^2 + (b - a \sin C)^2 - a^2 \sin^2 C \\ &= a^2 \cos^2 C + (b - a \sin C)^2 \geq a^2 \cos^2 C \end{aligned}$$
and similarly
$$\begin{aligned} a^2 + b^2 - 4S &= b^2 + (a - b \sin C)^2 - b^2 \sin^2 C \\ &= b^2 \cos^2 C + (a - b \sin C)^2 \geq b^2 \cos^2 C. \end{aligned}$$
Taking square roots and adding both together, we obtain
$$\sqrt{a^2 + b^2 - 4S} \geq \frac{a \cos C + b \cos C}{2}.$$
Equality holds iff $b = a \sin C$, $a = b \sin C$ and $\cos C \ge 0$. This condition is equivalent to $a = b$ and $\angle C = 90^\circ$. In a similar way we prove
$$\begin{aligned} \sqrt{b^2 + c^2 - 4S} &\ge \frac{b \cos A + c \cos A}{2} \quad \text{and} \\ \sqrt{c^2 + a^2 - 4S} &\ge \frac{c \cos B + a \cos B}{2} \end{aligned}$$
with equality iff $b = c$ and $\angle A = 90^\circ$, or $c = a$ and $\angle B = 90^\circ$, respectively. To finish, we recall that $c = b \cos A + a \cos B$ (see diagram)

as well as $a = c \cos B + b \cos C$ and $b = a \cos C + c \cos A$. Therefore, the semiperimeter is
$$s = \frac{a+b+c}{2} = \frac{c \cos B + b \cos C + a \cos C + c \cos A + b \cos A + a \cos B}{2}$$
and the desired inequality follows from adding the three earlier inequalities
$$\begin{aligned} & \sqrt{a^2 + b^2 - 4S} + \sqrt{b^2 + c^2 - 4S} + \sqrt{c^2 + a^2 - 4S} \\ \geq & \frac{(a \cos C + b \cos C) + (b \cos A + c \cos A) + (c \cos B + a \cos B)}{2} = s \end{aligned}$$
and noting that equality cannot occur, since there cannot be three right angles in a triangle.