No existe el Hard Reset total en Android, cuando haces un Wipe solo te borra las particiones Data y Cache. Si te has cargado algo de la /system te tocará reinstalar una ROM desde Odin si tienes un Samsung, del PC Suite si tienes LG, o de lo que sea que se use en el resto de móviles. O si tienes el Recovery CWM también lo podrás hacer así.
Haciendo wipes con el Recovery se deberían borrar también las claves del WiFi, algo debes estar haciendo mal.
En cuanto a la segunda ronda de preguntas:
1) Odin es una aplicación para PC, sirve para instalar una ROM es los teléfonos Samsung (y sólo en los Samsung) conectando el móvil por USB. Necesitas tener la ROM en el PC.
2) Titanium Backup está en el Market la versión gratuita, y si, para que funcione tiene que estar el móvil rooteado. Para Odin no hace falta que esté rooteado, de hecho puedes tener el móvil completamente muerto sin partición /system y también podrías flashear (siempre y cuando te funcione el combo de 3 botones en el PBL, es decir, el Modo Download)
3) Si