Freshbooks might actually let you do this - you can take a deposit from your clients. And once they pay apply a credit to their account, and then use a time tracker to bill "against" their credit on the account.

Most of my clients are prepaid but I hace certainly used it to bill against a credit amount .