Luis Ribes and I gave a proof of Nielsen-Schreier for open subgroups of free profinite groups that avoids using completions and the discrete Nielsen-Schreier theorem (well, actually our proof does both at once). We use wreath products instead. But we do use the Schreier basis. The ArXiv version is http://arxiv.org/pdf/0812.0027 and the final version is in l'enseignement mathématique.
Edit I think one could avoid the Schreier basis with our technique by using embedding problems like we do for quasi-free.
