In order to make this answer self-contained, I will repeat the first part of my answer to your other similar question.
First, show that for $N>2$, $\phi(\phi(N)) < N/2$. This can be done as such:
Let $N = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $N$ ($p_i$ prime, $k_i>0$)
- Suppose $N$ is even. Then $\phi(N) = N\prod_{i=1}^r(1-\frac{1}{p_i}) \leq N(1-\frac{1}{2}) \leq N/2.$ Thus $\phi(\phi(N)) < N/2$.
- Suppose $N$ is odd and $N > 1$. Then $\phi(N) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $N$. By the previous result $\phi(\phi(N)) < N/2$.
So we get the desired result.
Now, let $k>2$ be some fixed integer, and suppose $N\geq k^2$. You can write:
$$T(N) = T(\phi(N)) + 2T(\sqrt{N})+\lg(\phi(N))^3 $$
$$T(N) = T(\phi(\phi(N))) + 2T(\sqrt{\phi(N)})+\lg(\phi(\phi(N)))^3 + 2T(\sqrt{N})+\lg(\phi(N))^3$$
$$T(N) \leq T(N/2) +4T(N/k) + 2\lg(n)^3.$$
Where we used that $N\geq k^2 \implies T(\sqrt{\phi(N)}) \leq T(\sqrt{N}) \leq T(N/k)$ in the last step.
(Note that I am implicitly assuming $T(n)$ is a monotonically increasing function. One could get rid of that assumption by working on $S(n) = max(T(n),S(n-1))$, at the cost of making the argument more tedious and harder to follow)
Now we can apply the Akra-Bazzi method (a generalisation of the master theorem) with:
- $k = 2$
- $a_1 = 1$, $b_1 = \frac12$, $a_2 = 4$, $b_2 = \frac1k$
- $g(x) = 2\lg(x)^3$
First we need to find $p$ such that $a_1b_1^p + a_2b_2^p = 1$, that is: $$(\frac12)^p+4(\frac1k)^p = 1 \;\;\; (*)$$
Let's call $p_0$ the solution to $(*)$.
Then, we need to plug $p = p_0$ into the equation:
$$T(N) \in O(N^p(1+\int_1^N\frac{g(u)}{u^p+1}du))$$
To get:
$$T(N) \in O(N^{p_0}(1+\frac{6(N^{p_0}-1)}{p_0^4N^{p_0}\ln(2)^3})) \in O(N^{p_0})$$
(I just trusted WolframAlpha and did some simplifications for the integral, I'm too clumsy/lazy to attempt it myself if I don't have to)
Notice that in $(*)$ we can make $p_0$ arbitrarily close to $0$ by picking a big enough $k$. In other words, for any $\epsilon > 0$ there exists some $k>0$ such that $p_0 < \epsilon$. So let's pick any $\epsilon > 0$ and set $k$ such that $p_0 < \epsilon$. Plugging that into the last result we get:
$$T(N) \in O(N^\epsilon)$$
And this is true for any $\epsilon>0$.
In other words, $T(N)$ grows slower than any polynomial function in $N$.
I suspect it is asymptotically not much bigger than $\lg(\phi(N))^4$, as the square root term will vanish pretty fast, but I can't prove anything better than what I showed.
Also note that you could use the master theorem by setting $k=2$ and working on the upper bound $T(N) \leq 5T(N/2) + 2\lg(N)^3$, but this would of course lead to a much weaker result.