The problem is that I can't use the fact that elements of the same equivalence class have the same shape when written in cycle notation, because ...
Well, actually, we can use that fact. We just can't stop there. We can find the sets of permutations with the same cycle shapes, and then we'll have to check to see which of these split further into pairs of conjugacy classes.
$1+1+1+1$: The identity. A single conjugacy class of one element, which obviously doesn't split.
$2+2$: Pairs of disjoint transpositions. There are three of these, and they can't split. Why? Because any split would have to be into two subsets of equal size. Conjugation by a transposition would be a bijection between the two classes.
$3+1$: $3$-cycles. There are eight of these, and this set does split into two conjugacy classes of size $4$ each. As it turns out, a $3$-cycle and its inverse aren't conjugate in $A_4$; any even permutation which leaves the fixed element alone commutes with the cycle.
Alternately, we can prove this splits with an orbit-stabilizer count. $A_4$ acts on itself by conjugation, and the orbits are the conjugacy classes. The stabilizer of a $3$-cycle consists of all permutations that fix the fourth element not in that cycle, which are the powers of that $3$-cycle. That's a subgroup of order $3$, leaving room for four elements in the orbit. There's no way to get an eight-element orbit, because $\frac{12}{8}$ isn't an integer; the size of any conjugacy class must always divide the order of the group.
The other shapes are all odd permutations.
So then, the class equation is
$$|A_4|=1+3+4+4$$
No way to get $6$ out of that. Every subgroup contains the identity, so the only possible orders of normal subgroups are $1$, $1+3=4$, and $1+3+4+4=12$. All three of those possibilities are in fact normal subgroups in this case.
Best Answer
Let $x \in G$. $x$ is in a conjugacy class, $x^G = \{ g^{-1} x g : g \in G \}$, and $H \cap x^G \neq \varnothing$ by assumption, so let $h \in H \cap x^G$. Since $h \in x^G$, there is some $g \in G$ with $g^{-1} x g = h$ and so $x = ghg^{-1} \in gHg^{-1} \subseteq \cup_{g \in G} gHg^{-1}$.
Since $G$ is not in fact such a union (by the Lemma below), there is no such subgroup $H$. Every subgroup that intersects all conjugacy classes must not be proper, it must be all of $G$.
If $H$ is generated a set of representatives of the conjugacy classes, then it intersects every conjugacy class (for instance, in that chosen generator), and so it cannot be proper; instead $H=G$.
Lemma: No finite group is the union of conjugates of a proper subgroup.
Proof: [Standard and included in Hagen's answer] Let $G = \cup_{g \in G} gHg^{-1}$ for some subgroup $H \leq G$. Since $gh H = gH$ and $H(gh)^{-1} = Hh^{-1} g^{-1} = Hg^{-1}$, we don't need to union over all $g \in G$, since $g$ and $gh$ give the same subgroup $gHg^{-1} = ghH(gh)^{-1}$. We only need $[G:H]$ different $g$. Now consider the non-identity elements of $G$. Each one has to be in at least one of the $gHg^{-1}$, but it won't be the identity element of that subgroup. Hence the $|G|-1$ different non-identity elements of $G$ lie in one of the subsets $gHg^{-1} \setminus \{1\}$ of size $|H|-1$. Since there are at most $[G:H]$ of those subsets we get an inequality, $|G| - 1 \leq [G:H](|H|-1)$, but the right hand side is just $|G|- [G:H]$. Simplifying $|G|-1 \leq |G|-[G:H]$ gives $[G:H] \leq 1$, but since $[G:H]$ is a positive integer, this means $[G:H]=1$ and $H=G$. $\square$