When is a class function the character of a representation?

To clarify what I am specifically interested in knowing, if I have found some irreducible representations of a group $G$. Say I have $\chi_1, \dots, \chi_m$. I know I haven't found all of them because I know the number of conjugacy classes. Then, say, I some other non-irreducible character $\chi$ and I know, say, that this is the character of some representation. Then I subtract a linear combination of $\chi_1, \dots, \chi_m$, and define the class function $\psi = \chi - (a_1\chi_1 + \dots + a_m\chi_m)$. How do I know whether this $\psi$ is the character of some representation?

This question is much easier than your general question; assuming the $a_i$ are nonnegative integers, the answer is if and only if $\langle \chi, \chi_i \rangle \ge a_i$ for all $i$. This follows from:

Lemma: A class function $\chi$ is the character of a representation iff for every irreducible character $\chi_i$, $\langle \chi, \chi_i \rangle$ is a nonnegative integer.

Proof. If $\chi$ is the character of a representation $V$ then $\langle \chi, \chi_i \rangle$ is the multiplicity of the irreducible representation $V_i$ corresponding to $\chi_i$ in $V$, so this condition is clearly necessary. On the other hand, if this condition holds, then $\chi = \sum \langle \chi, \chi_i \rangle \chi_i$, and hence the direct sum of $\langle \chi, \chi_i \rangle$ copies of $V_i$ is a representation with character $\chi$. $\Box$

If you set $a_i = \langle \chi, \chi_i \rangle$ then you've removed the components of the representation corresponding to $\chi$ which correspond to the irreducibles with character $\chi_i$. So all you're left with is the components corresponding to the irreducibles you haven't found yet.

There is another angle at this. As so well-explained by @Qiaochu Yuan, if one knows the irreducible characters $\chi$ of the finite group $G$, then for some class function $\varphi$ you need to compute all inproducts $[\varphi,\chi]$ with these irreducibles and check if all the multiplicities are non-negative integers.

A different situation is that one has information about a set of subgroups $\mathcal{H}$, in the sense that $\varphi_H$ is indeed a character for all subgroups $H \in \mathcal{H}$. There is an old and famous result of Richard Brauer (sometimes referred to as characterization of characters) showing that indeed certain sets of subgroups $\mathcal{H}$ will guarantee that $\varphi$ is a character of $G$. This works for example if $\mathcal{H}=\{\text{all nilpotent subgroups of G}\}$. However, this "testing set" can be made smaller to what is called $p$-elementary subgroups: a $p$-elementary group is a direct product of a $p$-group and a cyclic $p'$-group.