Here is a bad algorithm, just to show that this is computationally doable. I don't know what a good algorithm would look like.
Step 1: Isolate the $\chi$ component of the group ring Let $\mathbb{C}[G]$ be the group algebra and $\chi$ the character. Define $\pi = 1/|G| \sum \chi(g) g^{-1} \in \mathbb{C}[G]$. Observe that $\pi$ is a central idempotent. Set $A=\pi \mathbb{C}[G] \pi$. So $A$ is a finite dimensional $\mathbb{C}$ algebra. We could calculate a basis for $A$ by starting with the spanning set $\{ \pi g \pi \}_{g \in G}$ and discarding duplicates, and we could work out how to multiply in that basis.
Now, from representation theoretic nonsense, we know that $A \cong \mathrm{End}(V)$ where $V$ is the representation we are looking for. Specifically, $\pi g \pi$ corresponds to the matrix in $\mathrm{End}(V)$ by which $g$ acts on $V$. If we could compute this isomorphism, we'd be in great shape.
Step 2: Find an isomorphism with a ring of matrices Choose $X$ a generic element of $A$. Computationally, just choose a random linear combination $\sum t(g) \pi g \pi$. Unless you got unlucky with your choice, $X$ with have distinct eigenvalues when acting on $V$. We will use the eigenvectors for those eigenvalues as a canonical basis for $V$ to write down our representation.
Let $d = \dim V$. Form the powers $1$, $X$, $X^2$, ... $X^d$ and, using basic linear algebra, find the polynomial $\sum a_i X^i=0$ they obey. Since $A$ is isomorphic to the $d \times d$ matrices, such a polynomial will exist. Now, at this point I am going to assume that you have a computer algebra system good enough to work with the roots of an arbitrary complex polynomial. I suspect this might be a problem in practice. Let $\lambda_1$, $\lambda_2$, ..., $\lambda_d$ be these roots. Let $P_i(t)$ be the polynomial $\prod_{j \neq i} (t-\lambda_j)/\prod_{j \neq i} (\lambda_i-\lambda_j)$. So $P_i(\lambda_j)=\delta_{ij}$. Set $\pi_i=P_i(X)$. So the $\pi_i$ are commuting orthogonal idempotents in $A$.
Let $e_{ij}$ be the element of $A$ with $\pi_i e_{ij} = e_{ij} \pi_j = e_{ij}$. The element $e_{ij}$ is unique up to scalar factor, and can be found by linear algebra. Once you get these scalar factors right, which I'll gloss over, you have constructed the isomorphism $A \cong \mathrm{End}(V)$.
Step 3: Profit! Write $\pi g \pi$ in the $e_{ij}$ basis. This is, in coordinates, the action of $g$ on $V$.