Update Abril 2015: Git Large File Storage (LFS) (por GitHub).
Utiliza git-lfs (ver git-lfs.github.com) y probado con un servidor que soporte: lfs-test-server:
Puede almacenar metadatos sólo en el repositorio git, y el gran archivo en otra.
Respuesta original (2012)
Una solución, para grandes archivos binarios que no cambia mucho, es almacenarlos en una referencia diferente (como un Nexus repository) y versión solo un archivo de texto que declara qué versión necesita.
El uso de un "depósito de artefactos" es más fácil que almacenar elementos binarios en un origen repo (hecho para comparar versiones y fusionar entre sucursales, que no es de mucha utilidad para dichos binarios).
La otra solución, más centrada en git, es git-annex:
git-annex permite gestión de los archivos con git, sin comprobar el contenido del archivo en Git.
Si bien esto puede parecer paradójico, es útil cuando se manejan archivos más grandes que git actualmente puede manejar fácilmente, ya sea debido a limitaciones en la memoria, el tiempo o el espacio en disco.
Sin embargo, no es compatible con Windows.
Una solución más genérica podría ser git-media, que también le permite usar Git con archivos de medios grandes sin almacenar los medios en Git.
Finalmente, la solución más fácil es aislar esos binarios en su propio git submodule como mencionas en tu pregunta: no es muy satisfactorio, y el clon inicial aún tomará tiempos, pero las próximas actualizaciones para el repositorio padre se breve.
He actualizado mi opinión con git-lts. – VonC