The key thing to remember is that what we (consultants) are not running a product business - we're a service business. We're not selling flour by the pound here. Clients will push for the product approach because it offers them the least risk: they know they will spend exactly X, and get exactly Y. The problem with this approach is twofold. First, it shifts all the risk onto us as consultants; second, it leaves either party unable to adapt to change without (potentially serious) personal cost. When changes happen (and they do: client decides a feature should work differently, timelines change for business reasons, etc), you and your client can't react to those changes because of the contract - unless you want to do some free work, which I can guarantee you don't.
Time and materials billing also encourages thorough work - in a fixed-rate project, it's a race to the finish so that you can keep as much of the bill as possible. This means taking shortcuts, exploiting technicalities in the contract, and other things that result in a sub-par final product (and business relationship). With T&M, you're motivated to make sure that features work exactly as intended, and the client is free to make as many changes as they like (at their expense of course).
Finally, if they complain "Oh, but you're just going to take longer to do everything so you can charge me more!", inform them that you have a long history of clients who have been very satisfied with your work, both in terms of final output and timeline. Testimonials are great here. If they push the issue, they don't trust you, and that's probably not going to lead to a good working relationship - proceed at your own risk.
I'm sorry that this doesn't answer your question - hopefully though, this advice will help keep you from running into similar situations in the future.
To weigh in on your current dilemma, It Depends (tm). If you value the relationship with the client and would like to continue working with them under the terms I outlined above, just swallow it and move on. If not, send them an invoice.
I would recommend incremental development, review, invoicing, payment so basically you're delivering modules/phases to the client so he can see/approve/pay for the work as things progress so you don't have too much time invested before the client sees the work and you see that he is paying.
If you just totally missed the mark with your quote and can't do the work for the amount you quoted it's probably better to stop work right away and be prepared to refund any up front payment they provided.
Then approach them to renegotiate the project fee/scope to an amount you are comfortable with. Or perhaps scale back some of the functionality to an initial version of the application for the fee they have authorized.
In any case if it's going to take a lot of your time to complete without proper compensation either scale it back to a scope that matches the agreed amount, get a new fee/scope approved, or honestly say the scope/features are beyond your original quote and you aren't going to be able to complete the work.
Just don't get hung up on a project that's going to eat up your time and doesn't provide you with proper compensation. You will resent working on it and I expect eventually you would give up on it and/or the client wouldn't receive the quality he was expecting.
If you're going back because you didn't do your job properly when you were gathering the project requirements and defining the scope you'll look like an amateur and you'll probably lose any future work from the client, but going back to the table to renegotiate even then is still an option. As far as the client is concerned it might well be better to pay you more money than have you give up on the project. Finding a new developer is hard. But don't assume they'll say yes to paying more either - sometimes finding a new developer is easier than sticking with one who ed up.