Well, in the first place, that's 8% of the federal budget, which seems like a pretty small price to pay for ensuring that everyone has a basic existence (minimal food/shelter). There are certainly stupider things we spend 8% of the federal budget on.
And in any case, one purpose is to be a replacement for the current piecemeal programs we have, which aren't cheap to begin with. Food stamps + Section 8 + EITC currently costs about $150 billion per year, plus some additional amount in bureaucracy and litigation due to complex rules, plus some additional economic damage caused by market distortion due to the fact that food stamps + section 8 aren't normal cash (EITC is better for that). That leaves maybe $100-150b, some of which is probably also redundant with existing welfare programs (I just picked three big ones), or about 3-4% of the federal budget.
If you want to keep it budget-neutral, how about an across-the-board 3-4% cut to all other budget categories in return? Or, we could just, as you point out, remove the temporary "overseas contingency operations" (Iraq/Afghanistan wars) supplement to the regular DoD budget, which is $125b in 2012, returning the DoD to its baseline budget. If I had a line-item veto pen I could pretty easily come up with another few hundred billion in savings if you'd like (cut agriculture subsidies, cut Medicare Part D, transition TSA/air-traffic-control to being fully user-fee-funded, do another round of domestic military-base closures through a BRAC-like process, etc., etc.). :)