Depends when you plan to get married and if there are vacant quarters (unlikely).
If you are getting married in a few weeks, they may let you take a place over soonish. If you are marrying in 10 years, then it is private hiring for you. there should be some stuff up in the welfare centres there, or try their Garrison Welfare Officer (i'm not at Herford, so don't know number - should be on Website).
You are entitled to shop in the NAAFI as a dependent, but as you aren't married, you aren't technically a dependent. You would be entitled to tax free stuff in your own right as a dependent, but as you aren't a dependent, you will have to buy tax free stuff with Fiance.
Again questions about your "status" as a fiance should be answerable by Welfare.
There are usually loads of jobs around Garrison - it depends on your skill set and past employment. If you were pulling in £30k a year you will be disappointed (unless you speak fluent German and can work "outside").
Agreed NAAFI is not always the cheapest. However you can get tax forms from mess etc which can be used in certain stores for tax free shopping (non rationed items). German VAT currently 19% so good savings to be made.
Once married you will be entitled to fuel coupons which give you tax free petrol/diesel.
As for jobs lots of dependant vacancies. When you get here buy the 6th sense paper available from the NAAFI.
What you need to do if your not getting married for a while, is get a civilian contract with Naafi,and then you can get a pass and all that cause if not I dont think your entitled to any of the dependants benefits e.g Camp pass unless he books you in every time, health services, you would need to get a AOK card etc, Naafi are always looking for people so it shouldnt be a problem. Youll love Germany make the most of it while your there. Good luck iwth the move and everything.