Solution:

Travel around the polygon in one orientation (say, counterclockwise), and let the vertices so visited be $x_{1}, x_{2}, \ldots, x_{n}$. Define $\Delta x_{i} = x_{i+1} - x_{i}$, for $i = 1, 2, \ldots, n-1$ and $\Delta x_{n} = x_{1} - x_{n}$. Define $\Delta y_{i}$ in a similar way. Then the perimeter is equal to
$$\sum_{i=1}^{n} \sqrt{\Delta x_{i}^{2} + \Delta y_{i}^{2}}$$
Since each length $\sqrt{\Delta x_{i}^{2} + \Delta y_{i}^{2}}$ is an integer, then for each $i$, either both $\Delta x_{i}$ and $\Delta y_{i}$ are even or exactly one is odd (they cannot both be odd using a mod-4 analysis). In the first case, we get an even length, and in the second case, we get an odd length.

So we need to show that the second case occurs an even number of times. This follows from the fact that
$$\sum_{i=1}^{n} \Delta x_{i} = \sum_{i=1}^{n} \Delta y_{i} = 0$$
Since $0$ is even, there are an even number of odd $\Delta x_{i}$'s and there are an even number of odd $\Delta y_{i}$'s.