It's a great question! Disappointingly, I think the answer to (2) is No :
The only restriction on a `good' division into "symmetric" vs. "symplectic" conjugacy classes that I can see is that it should be intrinsic, depending only on $G$ and the class up to isomorphism. (You don't just want to split the self-dual classes randomly, right?) This means that the division must be preserved by all outer automorphisms of $G$, and this is what I'll use to construct a counterexample. Let me know if I got this wrong.
The group
My $G$ is $C_{11}\rtimes (C_4\times C_2\times C_2)$, with $C_2\times C_2\times C_2$ acting trivially on $C_{11}=\langle x\rangle$, and the generator of $C_4$ acting by $x\mapsto x^{-1}$. In Magma, this is G:=SmallGroup(176,35), and it has a huge group of outer automorphisms $C_5\times((C_2\times C_2\times C_2)\rtimes S_4)$, Magma's OuterFPGroup(AutomorphismGroup(G)). The reason for $C_5$ is that $x$ is only conjugate to $x,x^{-1}$ in $C_{11}\triangleleft G$, but there there are 5 pairs of possible generators like that in $C_{11}$, indistinguishable from each other; the other factor of $Out\ G$ is $Aut(C_2\times C_2\times C_4)$, all of these guys commute with the action.
The representations
The group has 28 orthogonal, 20 symplectic and 8 non-self-dual representations, according to Magma.
The conjugacy classes
There are 1+7+8+5+35=56 conjugacy classes, of elements of order 1,2,4,11,22 respectively. The elements of order 4 are (clearly) not conjugate to their inverses, so these 8 classes account for the 8 non-self-dual representations. We are interested in splitting the other 48 classes into two groups, 28 'orthogonal' and 20 'symplectic'.
The catch
The problem is that the way $Out\ G$ acts on the 35 classes of elements of order 22, it has two orbits according to Magma - one with 30 classes and one with 5. (I think I can see that these numbers must be multiples of 5 without Magma's help, but I don't see the full splitting at the moment; I can insert the Magma code if you guys want it.) Anyway, if I am correct, these 30 classes are indistinguishable from one another, so they must all be either 'orthogonal' or 'symplectic'. So a canonical splitting into 28 and 20 cannot exist.
Edit: However, as Jack Schmidt points out (see comment below), it is possible to predict the number of symplectic representations for this group!
You seem to be asking for a description of the the algorithms in computational representation theory. I think that is far too broad a question for this site and you need to be more specific. There is a recently published book on this topic, which you might like to look at:
Representations of Groups A Computational Approach
Klaus Lux, Herbert Pahlings
Cambridge University Press, 2012.
Series: Cambridge Studies in Advanced Mathematics(No. 124)
As for the algorithms used by GAP, you can always look at source code! For example, for complex representations, the general approach is to compute the conjugacy classes and character table first, using the Dixon-Schneider algorithm for the latter, and a method of Dixon for getting the matrices of the representation from the character, which works if the group has a subgroup for which the restriction of the character has a linear constituent with multiplicity 1. For modular representations the Meataxe algorithm mentioned by Benjamin Steinberg is more effective.
The method you describe for finding conjugacy classes involving choosing random elements until you have covered all classes works well for groups that are not too large do not have very small conjugacy classes that are hard to find. For larger groups, there are better methods - I wrote something about this recently in
https://math.stackexchange.com/questions/198353/algorithm-to-find-conjugacy-classes-of-subgroups-elements-in-matrix-groups/198425#198425groups
BTW, I have no idea what you mean by "are there less complexity algorithms?"
Best Answer
The answer to your first question is negative. For a concrete example, you can show that the conjugacy class rings of the nonisomorphic groups $Q_8$ and $D_8$ are isomorphic, via an isomorphism that pairs off the bases as follows: $[1] \leftrightarrow [1]$, $[-1] \leftrightarrow [r^2]$, $[i] \leftrightarrow [r]$, $[j] \leftrightarrow [s]$ and $[k] \leftrightarrow [rs]$.
As to your question about the relationship between the conjugacy class ring and the character ring, there are lots of partial results that can be stated. Nonetheless, the answer to the question of when these two rings are isomorphic is completely known. This turns out to be the case if and only if the group is $p$-nilpotent with abelian Sylow $p$-subgroup. More generally, for arbitrary finite groups $G$ and $G'$, the following two conditions are equivalent.
The character ring of $G$ is isomorphic to the conjugacy class ring of $G'$.
$G$ and $G'$ are $p$-nilpotent groups with abelian Sylow $p$-subgroups. Moreover, if $g_1, \dots, g_l$ and $g_1',\ldots, g_{l'}'$ are complete sets of representatives for the conjugacy classes of $p'$-elements of $G$ and $G'$, resp., and if $D_i$ and $D_i'$ are Sylow $p$-subgroups of $C_G(g_i)$ and $C_{G'}(g_i')$, resp., then $l=l'$ and $D_i \cong D_i'$.
This is due to Saksonov, The ring of classes and the ring of characters of a finite group. Mat. Zametki 26 (1979), no. 1, 3–14, 156.