Wholly revised; my original idea cannot easily be patched.
$C_n$ is the number of ordered trees with $n+1$ vertices. There is a bijection between these and your sequences of length $n$ as follows. Do a depth-first search (or preorder search, if that terminology is more familiar) through the tree. When each node except the last is first encountered, write down the integer that is $1$ less than the number of children of that node. Ignore the last node.
For $n=3$, for instance, we have the following $C_3=5$ trees with their associated sequences:
* * * * *
| / \ / \ | /|\
* * * * * * * * *
| | | / \
* * * * *
|
*
0,0,0 1,-1,0 1,0,-1 0,1,-1 2,-1,-1
The inverse function is a bit harder to describe but not hard to illustrate. Say we have the sequence $2,1,-1,-1,-1$ for $n=6$; we can build the corresponding tree starting at the top. The root will have $3$ children. The traversal goes next to the first child, which must have $2$ children. Its first child has none, so it’s a leaf. Its second child is another leaf. And the traversal then goes to the root’s second child, which is a leaf. This of course leaves the root’s last child to be a leaf as well, and we have this tree:
*
/|\
* * *
/ \
* *
If you’ve not already seen the fact that $C_n$ is the number of ordered trees with $n+1$ vertices, there is a fairly easy bijection between these trees and balanced parenthesis strings. Do a complete depth-first traversal of the tree, starting and ending at the root, and record a left parenthesis when you go down an edge (i.e., away from the root) and a right parenthesis when you go up an edge. The five trees with $4$ nodes shown in the first diagram correspond in order to the strings ((())), ()(()), (())(), (()()), and ()()(); the tree with $6$ nodes shown above yields the string (()())()().
Added: Combining these bijections yields a direct bijection from your sequences to balanced parenthesis strings that isn’t too hard to describe. Given the sequence $\langle a_1,\ldots,a_n\rangle$, begin by writing down a row of $a_1+1$ matched pairs of parentheses and call the first pair the focal pair. Using the sequence $$\langle 3,0,-1,0,1,-1,-1,0,-1\rangle$$ as an example, I start with
$$\color{red}{()}()()()\;,$$
where the focal pair is red. Suppose that you’ve processed $a_k$ for some $k<n$. If $a_{k+1}\ge 0$, place a row of $a_{k+1}+1$ matched pairs of parentheses in the current focal pair and make the first of these pairs the new focal pair; in my example this results in the string
$$(\color{red}{()})()()()\;,$$
where the focal pair is again shown in red. If $a_{k+1}=-1$, however, as is now the case in my example, write nothing and shift the focus to the first empty matched pair to the right:
$$(())\color{red}{()}()()\;.$$
Continue in this fashion to complete the construction of the associated parenthesis string:
$$\begin{align*}
a_4=0:&\quad(())(\color{red}{()})()()\\
a_5=1:&\quad(())((\color{red}{()}()))()()\\
a_6=-1:&\quad(())((()\color{red}{()}))()()\\
a_7=-1:&\quad(())((()()))\color{red}{()}()\\
a_8=0:&\quad(())((()()))(\color{red}{()})()\\
a_9=-1:&\quad(())((()()))(())\color{red}{()}
\end{align*}$$
This is what I was fumbling towards in my original answer. The associated tree:
----------*----------
| / \ |
| / \ |
* * * *
| | |
| | |
* * *
/ \
/ \
* *
