I haven't heard this question before, but I would approach it in a following way: you know some basic relations between irreducible representations of a groups — e.g. their # is the # of conjugacy classes — and let's say we've written the kernels of representations and their dimensions. The generating function (*) that counts all representations is $((1-x^{r\_1})(1-x^{r\_2})\dots (1-x^{r\_k}))^{-1}$ and you're asked to subtract the representations that have nontrivial kernel. This combinatorial problem is partly tractable for a given group, though I don't see a nice closed formula.
The situation simplifies for Abelian groups, and the answer you provide is in the right direction. A semisimple representation of Abelian group is a sum of characters. (I misunderstood what you asked here a bit, but bear with me.) A single character could already be faithful: for example, for $\mathbb Z\_2 \times \mathbb Z\_3 = \mathbb Z\_6$ the irreducible character that hits all 6-roots of unity is a faithful representation. And there are $\varphi(6) = \varphi(3)\cdot\varphi(2) = 2$ of those. Another example: $\mathbb Z\_2\times \mathbb Z\_2$. The same formula doesn't works here as $1\cdot 1 = 1$ but the corresponding representation isn't faithful. For two-dimensional case, you positively get two characters, but there is no reason to expect that there will be a splitting into a character of exactly first summand and exactly second summand. You should, however, be able to calculate it by the method below.
So the formula $\prod\varphi(m\_i)$ will correctly describe the answer only for a case of group having only one invariant factor.
Here's how to make a complete computation for an $n$-dimensional space and the case of $\mathbb Z\_6$. You need to take all representations of it which are neither representations of $\mathbb Z\_2$ nor of $\mathbb Z\_3$. Fortunately, this is easy to write using inclusion-exclusion principle:
$(1 -x)^{-5} - (1-x)^{-1} - (1-x)^{-2} + 1$ and you can simplify this or just get the first three terms:
$1+5x+20x^2 + 5x^2 - 1 - x - x^2 - 1 - 2x - 3x^2 + 1 = 0 + 2x + 21x^2 + \dots$
The 2 here stands for 2 "simple" characters of $\mathbb Z\_6$, while 21, if I made no mistake, is the number of 2-dimensional representations: 19 of them are of the type "character as above $\oplus$ anything" and 2 of the type "character of $\mathbb Z\_2$ $\oplus$ character of $\mathbb Z\_3$ ".
Now I think using the same principle you can actually write a generating function for your sequence with an inclusion-exclusion principle for any group G. Since a representation is faithful iff it doesn't have a kernel, you can enumerate all of your normal subgroups and then find your answer as $F\_G(x) - F\_{G/H\_1}(x) - F\_{G/H\_2}(x) - \dots + F\_{G/H\_1\cup H\_2}(x) + \dots $. Here the notation $F\_G(x)$ is a generating function counting all representations and $H\_1, H\_2, \dots$ are all maximal normal subgroups.
Hope that helps.
Update: I understand now you're interested in a closed formula for a specific case. For example, the computation by the formula above for
$\mathbb Z\_2\times \mathbb Z\_2$ gives $(3\cdot 4)/2 -1 -1 -1 = 3$. The normal subgroups of an Abelian group are not hard to write, so it would be plausible if this could be made into a good formula.
(*) Let me know if you're not familiar with generating functions.
As requested by Faisal, I am posting as an answer the observation that if $G$ has more components than the size of the complex numbers then G has no faithful finite-dimensional irreducible representation over the complexes, for cardinality reasons.
To be honest I thought Faisal's response to this would be "what happens if $G$ has only countably infinitely many components"? That is then a different question. Does every countable group have a faithful finite-dimensional complex representation? If this is well-known I'd be happy to hear the answer. If it isn't I'd be happy if someone else asked this as a separate question. If it's true that any countable group has a faithful representation then one might ask about complex Lie groups with countably infinitely many components.
Best Answer
Take the complex Heisenberg group of 3 by 3 upper triangular unipotent complex matrices, and mod out by a subgroup $Z\times Z$ in the center.