Agreed, one should never start work with a new client without an advance. It doesn't need to be big, but get the client to put some skin in the game.
Also, regular progress payments are essential. You don't want to be in the hole 10k to someone when negotiating further work.
http://jamespmcgrath.com/progress-payments-based-on-mileston...
If they pay on PayPal or via their credit card, they can always do a chargeback.
I think, though, that a good method is to ask for an advance and maybe payments as the work progresses. I guess bad clients never pay advances.