* On ne sous-entend pas les articles, la notion d’article sous-entendu n’existe pas, et ces deux phrases sont aussi mal construites l’une que l’autre :
— Tête trempée, ils marchaient
— Têtes trempées, ils marchaient
Et un article n’améliorerait pas forcément grand chose.

* L’utilisation de l’article défini avec le sens d’un possessif, est fréquente pour les parties du corps :
— Le nez en l’air, les mains jointes… Il garde la tête droite. Ils gardent la tête droite.
Dans cette construction, l’article est distributif, et donc obligatoirement au singulier pour des têtes. La possibilité du pluriel n’existe pas.

* Il existe des expressions sans article, exprimant une façon d’aller ou d’être : tête nue, cheveux au vent…
Il y a parfois le choix, avec peut-être une nuance (description formelle ou attitude générale) : les mains dans les poches, mains dans les poches…
On peut probablement dégager une règle générale permettant cette construction, mais le plus sûr est de la réserver aux expressions déjà entendues, et « marcher tête trempée » n’en fait pas partie.

* Remarquez que vous n’avez pas envisagé le pluriel pour « épaule contre épaule« , ce qui montre que avez déjà une idée assez précise sur la question. Il ne s’agit évidemment jamais dans les expressions adverbiales de compter les épaules ou de compter les têtes.

* Par ailleurs, la construction « serrés les un les autres » n’est pas non plus possible.