(3) is most idiomatic.
"Always out of luck" is technically correct, but not idiomatic (as far as I've experienced as a US native speaker). Instead of "always out of luck", I suggest "I never have any luck", or "I'm always unlucky".
Also, "always" is stronger than "don't have much"; if someone has ever sought and found a job before, then technically neither #1 or #2 can be true. But #3 and #4 can be true if someone consistently has problems finding a job, regardless of whether they've had a job before.
The preposition ("in", "at", "on", etc) is trickier. In this case, I would generally prefer "in", because "in" is a bit more specific. "In" means that the bad luck is specifically isolated to the job search. Using "when seeking jobs" means that having bad luck is happening at the same time as seeking a job, but it's less clear that the bad luck applies only to seeking a job.
If I said, "I always have bad luck when the moon is full", it means that the moon being full is happening at the same time as my bad luck. If you feel like seeking a job impacts your luck in other areas, then "when" may be most appropriate. However, if you are specifically trying to say that you have difficulty finding jobs - but your luck is otherwise unaffected - then "in" is the better choice.