Yes, you can make money with free apps. A common approach is to develop a sophisticated app that people will be happy to pay money for, and then give away a free introductory version, with just a subset of the features. You must make it easy (and desirable) for people to upgrade. Only a small percentage will upgrade, but if you get the economics right, you can still make money.
As you say, another possibility is to give away an ad-supported version of the app. I've no experience of this, but I would be dubious that it would pay. I imagine the click-through rate would be relatively small on a mobile device, plus the income per click would be low as well, since it is harder for the advertiser to convert clicks into sales. But it might be worth trying.
Either way, the key to success is to develop a genuinely useful, high-quality app - one that people will talk about and want to download. Remember, there's an awful lot of competition in these markets.