The topological Hochschild cohomology (that I'll denote now THC) makes sense whenever $A$ is at least an $E_1$-algebra. In particular, you can construct THC of an $E_\infty$-algebra. There is a result called Deligne's conjecture but which is now a theorem stating that THC of an $E_1$-algebra is an $E_2$-algebra. In particular, if you take the homology of THC of something, the resulting graded abelian group has a Gerstenhaber algebra structure. If you take homotopy groups, you get a commutative algebra with a degree 1 bracket but I don't think it's going to satisfy the axioms of a Gerstenhaber algebra in general.

Taking the endomorphisms over $A\otimes S^{n-1}$ is a perfectly fine construction called higher THC. It can be defined as soon as $A$ is an $E_{n}$-algebra although the definition is slightly more involved (a good reference is http://www.math.northwestern.edu/~jnkf/writ/cotangentcomplex.pdf). Higher Deligne's conjecture tells you that this higer Hoschild cohomology is an $E_{n+1}$-algebra. In particular taking homology, you get a Gerstenhaber algebra with a bracket of degree $n$.

Note that in the case where $A$ is $E_\infty$, there is a nice construction of higher THC in the following paper of Ginot Tradler and Zeinalian (they restrict to $E_\infty$-algebras in chain complexes but the case of spectra is similar)
http://arxiv.org/abs/1205.7056