I think there is some structure to your problem, but I haven't fully thought this through. For example, if $\ell$ is prime then I think $k$ must be $1$ or $\ell$. Here are some thoughts on this case. Consider the odd elements $S_{o}$ in $S$ and the even elements $S_{e}$ in $S$. Your conditions impose the restrictions that the sumsets $S_o+S_o$ and $S_e+S_e$ are both at most as big as $S$ in size. If one views these sets just in ${\Bbb Z}/\ell {\Bbb Z}$ (relations are preserved in just viewing the congruences $\pmod \ell$) then this is very close to the extremal case of the Cauchy-Davenport theorem in set addition (since one of $S_o$ or $S_e$ must contain at least half the elements in $S$). In this situation the extremal cases are well understood -- this is known as Vosper's theorem and generalizations, and you would then be able to get the structure of $S_o$ and $S_e$. Essentially they look like progressions with maybe one term omitted. (Note that Zieve's examples look like this.) So you should be able to push this through to obtain a theorem at least for $\ell$ prime. For composite $\ell$ things are more complicated since there are more subgroups, and I don't think precise extensions of Vosper's theorem are known. There is an extensive literature on such inverse problems in additive number theory, and recent work by Serra, Zemor, Hamidoune, Rodseth and many others on this topic. Let me give a pointer to http://arxiv.org/pdf/math/0507561.pdf where you will find other references; also Serra's homepage will contain other papers.
Update: As the OP pointed out my guess that when $\ell$ is prime $k$ must be $1$ or $\ell$ is not correct. What does follow from the inverse theorems referred above I think is that when $\ell$ is prime and $k<\ell$ then $S$ decomposes as the union of $S_o$ and $S_e$ and that each of these sets forms an arithmetic progression missing possibly one term.
**More precise version:** Here's a more precise version of my comments above. I will assume below that $\ell$ is an odd prime. First we reformulate the problem. Let $S$ be a subset of cardinality $k$ in ${\Bbb Z}/2\ell {\Bbb Z}$ such that no two elements in $S$ are congruent $\pmod \ell$. Let $S_o$ and $S_e$ denote the odd and even elements in $S$. Denote by $2\times S$ the set $\{ 2s: s\in S\}$, so that $2\times S$ also has cardinality $k$. The problem asks for the structure of $S$ given that $S_o+S_o=S_e+S_e = 2\times S$.
If $k =\ell$ there are many such sets and there is no structure. To see this choose a random set of $(\ell+1)/2$ residue classes $\pmod \ell$ and lift these to a set $S_o$ of odd residue classes $\pmod {2\ell}$. Take the complementary set of $(\ell-1)/2$ residue classes $\pmod \ell$ and lift these to the set $S_e$ of even residue classes $\pmod {2\ell}$. With high probability $S_o+S_o =S_e+S_e = \{0, 2, 4, \ldots, 2\ell -2\}$.
If $k=\ell -1$ there is a similar construction. From every pair $i$, $\ell-i$
($1\le i\le (\ell-1)/2$) choose a random number, and lift these $(\ell-1)/2$ numbers to a set $S_o$. Take the complementary choice and lift that to a set $S_e$. Then with high probability $S_o+S_o = S_e+S_e =\{2,4,6,\ldots, 2\ell -2\}$.
If $k$ is not too close to $\ell$ then one gets structure. This follows from the Hamidoune-Rodseth version of Vosper's theorem that I mentioned above. Precisely suppose that $8\le k\le \ell -4$. Suppose that $S_o$ contains at least $k/2$ elements (similar argument if $S_e$ is the bigger set). From the Cauchy-Davenport theorem one gets that in fact $S_o$ must be of size $\lceil k/2\rceil$ (and so $S_e$ contains $\lfloor k/2\rfloor$ elements). Then from the Hamidoune-Rodseth theorem we find that $S_o$ must be an arithmetic progression missing possibly one term. If $k$ is even, the same conclusion applies to $S_e$. If $k$ is odd (so that $S_o$ has $(k+1)/2$ elements and $S_e$ has $(k-1)/2$ elements) then one needs the stronger result of Serra, Zemor and Hamidoune, and here $S_e$ can omit two elements from an arithmetic progression (if $\ell$ is at least $53$).