Yes, this is possible. But I'm not sure how to turn your strategy into a proof, because you don't seem to be using the fact that the group is finitely generated, so why wouldn't your proof work with any group action on a tree?
Here's a proof. In fact, you do not need to assume the tree is locally finite, and you do not need to assume the edges have finite stabilizers. All you need to do is to construct a $G$-invariant subtree $T'$ that has finitely many orbits of edges (and, hence, a finite orbit graph $G/T'$).
To do this, let $g_1,...,g_K$ be a finite generating set for $G$. Choose a vertex $x \in T$.
For each $k=1,...,K$ let $p_k$ be the path in $T$ that connects $x$ to $g_k \cdot x$.
Let $T' = \cup_{h \in G, k\in \{1,\dots, K\}} (h \cdot p_k)$.
By construction $T'$ is a $G$-invariant subgraph of the tree $T$. Also, there are finitely many $G$-orbits of edge of $T'$, because each such orbit has a representative edge in the finite subgraph $p_1 \cup \cdots \cup p_K$. It remains to prove that $T'$ is connected, for then it must be a tree.
To prove connectivity, take any vertex $y \in T'$, and so there exists $h \in G$ and $k' \in 1,...,K$ such that $y \in h \cdot p_{k'}$. Note that the initial vertex of the path $h \cdot p_{k'}$ is $h \cdot x$.
Now factor $h$ into a word in the generators, $h = g_{k(1)} \cdots g_{k(M)}$.
Then by concatenating translates of the paths $p_k$ you get a path $q$ in $T'$ from $x$ to $h \cdot x$ as follows:
$$q = p_{k(1)} * (g_{k(1)} \cdot p_{k(2)}) * (g_{k(1)} g_{k(2)} \cdot p_{k(3)}) * ... * (g_{k(1)} g_{k(2)} ... g_{k(M-1)} \cdot p_{k(M)})
$$
Note that the terminal vertex of this path $q$ is
$$g_{k(1)} g_{k(2)} ... g_{k(M-1)} \cdot (g_{k(M)} \cdot x) = h \cdot x
$$
So the concatenation of $q$ with the subpath of $h \cdot p_{k'}$ connexting $h \cdot x$ to $y$ is a path in $T'$ from $x$ to $y$.