I wanted to post this generalization after seeing these problems: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=468314#p468314 http://www.artofproblemsolving.com/Forum/viewtopic.php?p=468314#p468314 If $S$ does not meet every connected component of $G$, then it's easy to take care of the components disjoint from $S$: just assign the value $0$ to each point in such a component. This means that it suffices to restrict our attention to the case when $S$ does meet every component, and in this case the proof in that first link works, with only the obvious modifications (that last argument in that topic basically says that in that particular case, $S$ meets every component; since here we're already assuming this, no such argument is needed).

Let $T = V(G) / S.$ We interpret the desired labelling as a system of equations. Consider the adjacency matrix $A$ of the vertices in $T$, with the one difference that we write $-deg(v_i)$ along the main diagonal. In this way, the problem's condition can be interpreted as: $$A \cdot v = v',$$ where $v$ is the vector of the labellings of the elements of $T$, and $v'$ is some fixed vector. We need to show that this has a solution. First of all, as grobber did above, we can WLOG assume that there is no connected component in which $S$ contains no elements. With this assumption, we're ready to show that the rows of $A$ are linearly independent. Indeed, suppose that they were not for contradiction. Then, if we let $r_i$ be the vector corresponding to the $i$th row of $A$, then there exist real numbers $x_i$ so that $$\sum x_ir_i = 0.$$To see that this cannot occur, consider the largest $x_i.$ Then since $-x_ideg(v_i)$ must be summed with other terms to make the $i$th coordinate zero, we know that all neighbors $v_j$ of $v_i$ must be in $T$, and have $x_j = x_i.$ If we continue this logic, we get that the connected component of the subgraph of $G$ spanned by $T$ which contains $x_i$ is adjacent to no vertices of $S$, i.e. it should've been removed by the above assumption, contradiction. $\square$

Another approach. The idea is at first to assign some number to each vertex of $V(G)\setminus S$ and then iterate assigning to each vertex of $V(G)\setminus S$ the average of its neighbours. If the corresponding real sequences, obtained for each vertex, converge then their limits will do the job. It's not certain that each initial assigning will bring convergence, it's even not true, but we show it holds for a specific initial assignment. To begin with, it's enough to prove the claim when all numbers assigned to $S$ are non negative. Indeed, in general case, we can represent each number in $S$ as difference of non negative numbers, then get missing numbers to both configurations and finally subtract vertex-wise corresponding values. So, we may assume the assigned numbers to $S$ are non negative. Let $M$ be the maximal number assigned to $S$. By $v^{k}_j$ we denote the number assigned to the vertex $v_j\in V$ at step $k$. We set the initial assigning as $v^{(0)}_j:=M\,,\,\forall j,v_j\notin S $. We construct inductively the sequence $v^{k}_j, k=1,2,\dots$ $$ (*)\,\,\,\,\,\,\,\, v^{(k+1)}_j:= \begin{cases} \displaystyle \frac{1}{|N(v_j)|} \sum_{v_i\in N(v_j)} v^{(k)}_i\,,& v_j\notin S\\ v^{(k)}_j\,,& v_j\in S \end{cases} $$where $N(v_j)$ denotes the set of verticies adjacent to $v_j$ . Clearly $v^{(1)}_j\leq v^{(0)}_j\,,\,\forall v_j\in V$. Now, by induction, applying $(*)$, we conclude $v^{(k+1)}_j\leq v^{(k)}_j\,,\,\forall v_j\in V;k=0,1,\dots$ . It means the sequence $v^{(k)}_j$ for fixed $j$ and $k=0,1,\dots$ is monotonically decreasing and non negative, hence it converges to $v^*_j$. Finally, taking the limit in $(*)$, we conclude the assignment $v^*_j$ satisfies the requirement.