As Geoffrey mentioned, exclusive content and deals work very well on Facebook, especially because Facebook makes it very easy to integrate these into your Page using custom tabs.
The simplest solution for a coupon on Facebook might be a fan gated custom tab, with a form where the user can enter his email address to receive the coupon or simply with a PDF coupon to download. The application for this can be coded quickly and you can reuse the code later for other similar campaigns.
However I think it’s also important to take fan engagement further than just offering them coupons and contests. Make sure to answer to messages on your wall (especially complaints) and to organize games or contests just for fun. If users feel connected to your brand, they will come back to your stores, even without a coupon.