Regarding the edit: I think natural density should still be easier for Frobenius. Let $G$ be $\mathrm{Gal}(F/\mathbb{Q})$ and let $c$ be a class function $G \to \mathbb{C}$.
Cebatarov with natural density is the statement
$$ \sum_{p \leq N} c(\mathrm{Frob}(p)) \sim \left( \sum_{g \in G} c(g) \right) \cdot \pi(N) $$
Frobenius is the special case of a class function where $c(g)=c(h)$ whenever $g$ and $h$ generate the same cyclic subgroup.
In both cases, the set of such class functions is a vector space, so it is enough to prove this for a spanning set of class functions. In the Cebatarov case, the spanning set is inductions of one dimensional characters of subgroups $H$ of $G$. In the Frobenius case, it is enough to induct only trivial characters.
Let $H$ be a subgroup of $G$, let $L$ be the fixed field and let $\chi: H \to \mathbb{C}^{\ast}$ be a character. Let $K \subset H$ be the kernel of $\chi$ and let $M$ be the fixed field of $K$, so $M/L$ is an abelian extension.
Then I believe (this is the part I am not sure of) that Cebatarov for $\mathrm{Ind}_H^G \chi$ should reduce to showing that $L(M/L, \chi)(s)$ has no zeroes or poles on $\mathrm{Re}(s)=1$, except for a simple pole at $s=1$ for $\chi$ trivial. (For Dirichlet density, we only need to show this at $s=1$.) Frobenius amounts proving this only in the case that $\chi$ is trivial. In this case, we are trying to show that $\zeta_L(s)$ has no zeroes or poles on $\mathrm{Re}(s)=1$, except a simple pole at $s=1$.
So the key question is, are the easiest proofs that $\zeta_L(s)$ has no zeroes or poles on the critical line easier than the corresponding proofs for $L(M/L, \chi)(s)$? I think the answer is yes. The proofs that I am aware involve two main parts
(1) Show that the function in question has no poles (other than the stated one at $s=1$) on $\mathrm{Re}(s)>0$.
(2) Write down some clever product of various $L$-functions which is manifestly non-vanishing, and conclude that none of the factors can vanish. This argument requires (1) to have been already done, to rule out the possibility that a zero and pole cancel.
Now, I don't know whether (2) gets significantly easier when $\chi$ is trivial. But (1) definitely does! The fact that $\zeta_H(s)$ extends to $\{ \mathrm{Re}(s)>0,\ s \neq 1 \}$ follows from the same sort of computations that lead to the class number formula for number fields. For $L$ functions, the way I know how to do it requires first proving that the character $\chi$ on $\mathcal{O}_L$ is periodic, so that we can group together sums over a complete period and guarantee that they converge. This is equivalent to Artin reciprocity, which as far as I know is as hard as all of class field theory.
Chebatarov's original proof (see the last section of Lenstra and Stevenhagen) avoids this. To my limited understanding of this, Cebatarov first proves the result when $M$ is a cyclotomic extension of $L$, where Artin reciprocity is easy, and then some how cleverly reduces to this case. But, even so, it seems to me that it must be easier when we work with just trivial characters.
