Ad click prediction: what are the negative examples?
You're overthinking it.  You might not need a threshold.  Start with the simplest approach you possibly can: If you showed the ad to a visitor, then that's a negative example.  Each time you show an ad to a visitor, you end up with an instance, whether positive or negative.  If you've showed the ad three times to the same visitor, you end up with three examples.  (Maybe all negative; or maybe one is positive and two are negative; but that's fine.)

Bonus tip: Do research methods for handling class imbalance.