Faits: A. Le divorce des époux X._ a été prononcé par jugement du Tribunal de première instance du canton de Genève du 29 novembre 2010. L'autorité parentale et la garde sur leurs deux enfants communs, A._, né en 1997, et B._, née en 2001, ont été attribuées à la mère. Jusqu'au jugement, B._ était inscrite à l'École C._, distante de 500 mètres environ de l'ancien domicile conjugal où vit le père. Une distance de près de quatre kilomètres sépare en revanche cette école du domicile actuel de la mère, l'école la plus proche étant celle de D._ située à 300 mètres seulement. Dès le 17 janvier 2011, la mère s'est adressée au Service de la protection des mineurs (ci-après: SPMi) pour organiser le changement d'école que requéraient les autorités scolaires. Des contacts ont été pris avec les directions des établissements concernés et la date du changement a été arrêtée au 28 février 2011, date de reprise des cours après les vacances de ski. L'enfant et le père ont été informés de cette décision avant le début des vacances. B. Le 22 février 2011, X._ a requis une mesure de protection de l'enfant doublée d'une requête de mesures provisionnelles d'extrême urgence en vue du maintien de l'enfant au sein de l'École C._ lors de la rentrée du 28 février 2011. Statuant sur mesures provisionnelles urgentes, avant audition des parties, le Tribunal tutélaire du canton de Genève a fait droit à cette requête par ordonnance du 23 février 2011. Le 28 mars 2011, après audition des parties et instruction écrite, ledit Tribunal a admis l'opposition de la mère et annulé sa précédente ordonnance. Statuant sur recours du père, la Cour de justice du canton de Genève l'a rejeté par décision du 6 juin 2011. C. Le 8 juillet 2011, X._ exerce un recours en matière civile contre cette décision, concluant à son annulation. Il requiert en outre que l'enfant soit entendue, que l'ordonnance du 23 février 2011 soit confirmée, que le maintien de B._ au sein de l'École C._ soit ordonné, qu'il soit fait interdiction à l'intimée d'inscrire l'enfant à l'École D._ ou dans toute autre école ainsi qu'il soit constaté que l'autorité parentale de la mère sera limitée sur ce point. Préalablement, il demande l'octroi de l'effet suspensif et de l'assistance judiciaire gratuite. À l'appui de ses conclusions, il se plaint de la violation des art. 296 et 307 ss CC ainsi que des art. 9 et 29 Cst. Suite à la détermination de l'intimée, qui a conclu au rejet de la requête d'effet suspensif et a requis l'assistance judiciaire gratuite, la Présidente de la Cour de céans a attribué l'effet suspensif au recours par ordonnance du 19 juillet 2011. Aucune observation n'a été requise sur le fond.