If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)
The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.
We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.
So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.
We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $
The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.