You say "we" so I presume that's you and your spouse. Are all 6 scores under 600?
Mortgage broker is your best bet. You'll almost certainly be in subprime territory. Unless the payment is absolutely not possible, you could always take the subprime today, work on your credit over the next year, and then check into whether you can get prime in a refi.
If you aren't already working with a broker, feel free to PM me. I can point you to one you might be able to help you.
If you can document your income you have a much better chance to get financing. If you cannot document your income, then you will need a minimum of 5% as a down payment. (5% may not be enough)
It can be done if the everything lines up correctly, but it will be difficult.
What's your CC util? For a 2 point bump, that's probably the fastest way to get there, and then some.