The best way to do it (for tracking) is with some sort of pre-paid deal. But it has to be structured to make it worthwhile for all involved.
With the gas station scenario, a customer can go to your site and buy a $10 gas certificate and take it to the gas station to redeem for gas. The gas station then gives it to you to redeem for cash. Since the station has to redeem it with you to get paid, you'll have a good count for all the leads.
No for the hard part- how do you make the customer buy it from you? If you charge $10, there's certainly no incentive for him to buy it from you instead of just directly from the gas station. Even for $9, it's probably not worth the $1 savings to print the coupon and remember to take it to the gas station. For $5? More likely.
However, is the gas station going to pay you $5 for the lead? (In other words, he gives the customer $10 of gas, but only gets $5 back from you.) And even if he does, that's only break even for you. A loss actually, once you factor in the credit card processing fees for the online transaction.
Now, you can (and should) argue that the gas staion is only out the PROFIT he could have gotten from that $10 of gas. Plus the customer will most likely buy more than $10 of gas (especially at today's prices!) and maybe even some other high profit items like a Coke and a bag of Cheetos while he's there. So the gas station's "cost" is actually a lot less than a $5 lead.
Depending on the business, even a $10 customer acquisition cost is a bargain. But at least this gives you one example of how to do it.