Let $C_1,C_2,\ldots,C_n$ be the conjugacy classes of a finite group $G$. It is possible that there are two non-conjugate subgroups $K \leq G$ and $H \leq G$ such that $|H \cap C_i|=|K \cap C_i|$ for all $i = 1,\ldots,n$?

Yes, this is precisely the definition of a *Gassmann triple*. Your condition is equivalent to the permutation representations $\mathbb{C}[G/K]$ and $\mathbb{C}[G/H]$ being isomorphic. I believe that the smallest example (in terms of $[G:K]$) is $G=SL_3(\mathbb{F}_2)$, $K$ the stabilizer of a line in $\mathbb{F}_2^3$ and $H$ the stabilizer of a plane.