Dans cette phrase, tout est un adverbe qui modifie petit  (il est remplaçable par très par exemple). Il est donc invariable : Nous nous sommes connus tout petits.
À noter que, de manière anormale, un accord se fait quand même au féminin : Elles se sont connues toutes petites. Il  s’agit là d’une forme non orthodoxe imposée à une époque lointaine par l’Académie française mais toujours en vigueur. 
À noter aussi la différence avec Nous nous somme tous connus petits qui a un autre sens.