Têtes découvertes et trempées par le crachin, ils se tenaient les mains, serrés les uns les autres, épaule contre épaule. On peut considérer la totalité des têtes. Ce pluriel semble assez logique.
Tête découverte et trempée par le crachin, ils se tenaient les mains, serrés les uns les autres, épaule contre épaule. On peut considérer « une tête par personne » et garder le singulier.

* 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.

Je me permets de soulever quelques maladresses dans votre phrase :
O Personnellement, j’emploierais le singulier pour « tête« , car cela revient à dire –> ils avaient la tête découverte.
Je ne pense pas que l’on puisse dire : ils se tenaient là, têtes découvertes / têtes nues… on dira plutôt « ils étaient tête nue » (chacun était tête nue), mais évidemment  je peux me tromper :°)
O À mon sens, ce ne sont pas les têtes qui sont trempées, mais les cheveux.
O « Serrés les uns les autres  » ne se dit pas. Ils sont serrés les uns contre les autres.
O « épaule contre épaule » ne peut pas s’écrire au pluriel, car (à moins d’être vraiment très souple…) on ne peut toucher quelqu’un qu’avec une seule épaule.
Voici ma suggestion :
Tête nue (découverte) et les cheveux trempés par le crachin, ils se tenaient les mains, serrés les uns contre les autres, épaule contre épaule.

Merci pour ces précisions et ces remarques très pertinentes. Serrés les uns contre les autres, bien sûr ! Où avais-je…….. la tête ?!