Functions that link to divisor function

Such a function does exist; here’s an explicit construction.

Take each $n\in\mathbb N$ in ascending order, assigning a function value $f(n)$ (and possibly further function values), starting with $f(1):=1$ and $f(2):=2$, which you’ve already shown to be required. If we haven’t assigned a function value for $n$ yet, check whether we have already assigned $\sigma_0(n)$ as a function value $f(m)$ for some $m$. If so, assign $f(n):=m$. (This step isn’t actually necessary, it just prevents an even more rapid growth of the function values.) If there is no such $m$ yet, find the least prime $p$ such that $r=p^{f(\sigma_0(n))-1}$ has not been assigned a function value yet. (Since $\sigma_0(n)\lt n$ for $n\ge3$, we have already assigned a function value for $\sigma_0(n)$ when we reach $n$.) Assign $f(n):=r$ and $f(r):=\sigma_0(n)$. (This ensures $f(f(n))=f(r)=\sigma_0(n)$ and $f(f(r))=f(\sigma_0(n))=\sigma_0(r)$.) The least such prime $p$ is used just to keep the numbers small (and to avoid having to use the axiom of choice); any such prime $p$ would do.

Here are the function values assigned by this construction to the integers up to $59$, each line showing $n\to f(n)\to f(f(n))$:

1 -> 1 -> 1
2 -> 2 -> 2
3 -> 2 -> 2
5 -> 3 -> 2
4 -> 5 -> 3
16 -> 4 -> 5
6 -> 16 -> 4
7 -> 3 -> 2
8 -> 16 -> 4
9 -> 7 -> 3
10 -> 16 -> 4
11 -> 3 -> 2
32768 -> 6 -> 16
12 -> 32768 -> 6
13 -> 3 -> 2
14 -> 16 -> 4
15 -> 16 -> 4
17 -> 3 -> 2
18 -> 32768 -> 6
19 -> 3 -> 2
20 -> 32768 -> 6
21 -> 16 -> 4
22 -> 16 -> 4
23 -> 3 -> 2
14348907 -> 8 -> 16
24 -> 14348907 -> 8
25 -> 23 -> 3
26 -> 16 -> 4
27 -> 16 -> 4
28 -> 32768 -> 6
29 -> 3 -> 2
30 -> 14348907 -> 8
31 -> 3 -> 2
32 -> 32768 -> 6
33 -> 16 -> 4
34 -> 16 -> 4
35 -> 16 -> 4
64 -> 9 -> 7
36 -> 64 -> 9
37 -> 3 -> 2
38 -> 16 -> 4
39 -> 16 -> 4
40 -> 14348907 -> 8
41 -> 3 -> 2
42 -> 14348907 -> 8
43 -> 3 -> 2
44 -> 32768 -> 6
45 -> 32768 -> 6
46 -> 16 -> 4
47 -> 3 -> 2
30517578125 -> 10 -> 16
48 -> 30517578125 -> 10
49 -> 47 -> 3
50 -> 32768 -> 6
51 -> 16 -> 4
52 -> 32768 -> 6
53 -> 3 -> 2
54 -> 14348907 -> 8
55 -> 16 -> 4
56 -> 14348907 -> 8
57 -> 16 -> 4
58 -> 16 -> 4
59 -> 3 -> 2

The reason I’m including the list only up to $59$ is that with $\sigma_0(60)=12$ and $f(12)=2^{15}$ already assigned, the next assignment is $f(60)=2^{2^{15}-1}$, a number with about $10^4$ digits.

Here’s Java code that implements the construction.