Son muchas cuestiones pero mas o menos intentaré ser breve bajo mi punto de vista, por orden:
Como te han dicho los albergues gratuitos estan reservados a los sin techo, pero es fácil dormir en un Hostel que le llaman ahora de forma cómoda por menos de 20€ en cualquier ciudad.
Repostar agua, bueno como ya ha dicho algún compi, no te cortes en pedirla de no haber agua en ninguna fuente cercana, la gente suele ser amable en estos aspectos.
No no pasa nada y es lo mas conveniente, nadie te va a molestar, ubicate en una buena zona tranquila y al ruesgardo del viento y la guardia civil y con los últimos minutos de luz monta la tienda.
Yo en ocasiones en los que no era posible acampar a las afueras de un pueblo (metido en medio de unos cortados o cosas por el estilo) siempre he preguntado y al menos en Andalucía siempre me han dirigido hacia una zona o bien de acampada controlada o un área recreativa donde jamás me ha molestado nadie.
No te preocupes tanto por la seguridad, estamos bombardeados por las noticias y parece que en cualquier momento nos van a querer matar o robar. No creo que un ciloturista sea un primer objetivo a robar, si estas durmiendo en el campo no creo que piensen que escondes fajos de billetes.
El tema de la navaja ya esta muy aclarado, yo llevo una táctica Böker de 12cm creo y como no voy haciendo alarde de ella, jamás me han dicho nada, vamos, ni sabrian que llevo nada encima.
Siempre hay una manera de llegar que no sea autovía, siempre. yo te recomiendo que te vayas familiarizando con los mapas del ministerio del interior (rapster) con los escala 50 ya es mas que suficiente y detallan cualquier camino de cabras. Los caminos y senderos deben ser tu primera opción y por último las carreteras secundarias, olvidate de nacionales o ya autovías ni mencionar.
En nacionales hay algunos tramos buenos y tranquilos, la n340 por málaga es un buen ejemplo de ello, salvando ciertos puntos como pueden ser marbella y motril con un tráfico muy denso, pesado y estresante, por no decir peligroso.
El tema de la comida, si es por andalucía, la verdad es que es recomendable pararse en un bar y tomar alguna ración o tapas no es nada caro y no repercute mucho en la economía. Lo suyo es pequeño hornillo multifuel y comprar en el super del último pueblo de cara a la cena para no llevar cargando peso durante toda la ruta. Plato que siempre recomiendo facil, rapido barato y perfecto para el esfuerzo es arroz cocido (ya venden cocido y no se pone malo sin frio) revuelto con garbanzos ya cocidos y atún o salchicas.
Es muy saludable da una energía tremenda que libera poco a poco y no se siente pesadez.
Espero haberte ayudado algo. Un saludo.