Solution:
The possible perimeters are all even numbers greater than $2$. To show that these are all possible, note that a $1 \times (n-1)$ rectangle has perimeter $1 + (n-1) + 1 + (n-1) = 2n$, so there is a shape with perimeter $2n$ for every $n \geq 2$. To show that no shape can have odd perimeter, imagine walking along the boundary of the shape starting from some point and coming back to the same point. For every step to the right, you must also take a step to the left at some point, and for every step up, you must also take a step down at some point to end up back where you started. Thus, the total number of steps must be even.