Is is possible to deduce that every integer is divisible by a prime from the fact that the set of integers not divisible by a prime has natural density zero?
Preferably, I would not be looking for, "Yes, by a classic proof.", but rather some number-theoretic trickery with the above fact or some deductions from really elementary ideas about numbers.
No, because a set with natural density zero can still have members. For example the powers of $2$ have natural density $0$, but we cannot use that to prove that there are no numbers that are powers of $2$.