The bottom line is that you need to establish a relationship with the client. If they don't trust you to bill them fairly - they why are they trusting you to do the work correctly? Of course you know that, since you're asking how to establish that kind of relationship with new clients.
Here's a couple of ways:
Do something small first. If you can, pick a simple deliverable, where the client has a good idea of what time it should take. This doesn't prove that you'll be honest about things when the client doesn't have a good understanding of the time it should take, but the goal is to find something you both can be comfortable with at the start - to establish the trust needed down the road. Before signing that big contract, find something small to do. This also helps avoid costly, drawn-out interviews, as it's essentially a paid trial.
Overestimate your time. At the start, if you consistently beat your estimated time, your new client will realize you're not trying a bait and switch. At the core, their fear is that they'll approve some project / task assuming a cost, and that cost will grow. Under-estimating to get approval will break their trust as much as padding hours. But at least you can prove you're not doing the former. For this to work well, you need to give estimates on small tasks, not large projects.
Outsource the trust (at least to start things off). This is going to probably be the most controversial. I'm a full time contractor / freelancer, and I do all my hourly billing through oDesk (and have done that for years). One reason I do that is they make it easy for me to trust that the client will pay me (they guarantee payment), and they make it easy for the client to verify that I'm working (they take random screen shots, and record keyboard / mouse activity levels). And that helps both parties feel comfortable when there's no prior relationship (a cold contact, not a referral through someone you mutually trust).
I do all three regularly. I don't estimate large projects, I work with new clients to find the smallest possible thing we can build - so they can feel comfortable spending a little money to evaluate my actual work. I also overestimate the time on that first deliverable. Yes, I loose some potential clients because of that - but I don't really want clients that are so tight on their budget that there no wiggle room. In that way, the process is a kind of trial run from my perspective as well.
And as mentioned, I use oDesk for all my hourly contracts. Even if the client contacts me directly, I have them signup and hire me through the platform (for more reasons than what is stated above).
I'm a contract developer, this works well (I believe) for the kind of work I do. It may not work well for other kinds of contracting / freelancing, but I think it's at least worth considering.