It doesn't really work that way. Most people who don't "get" predestination (or don't believe it) think it is something to worry over in the manner you described. What it basically means is that only people who are predestined to believe will believe. Taking the guy in your example: if he was a believer, then he was predestined to be a believer. You don't have to believe in predestination to be a believer.
If there is anything "scary" about it, it is that some people will not be predestined to believe. A lot of people have a problem with the idea that God chooses who will believe and that some will not be chosen.
RE: A lot of people have a problem with the idea that God chooses who will believe and that some will not be chosen.
Yes, that is the crux of the matter. Someone described it as a toy maker making 20 toys and decides before making them that after making all of them, 10 of them will be thrown into the fire.
A good example of this that helped me understand is: Imagine in heaven there is a door you enter that on the front of it says: "Whosoever will..." and once you get inside, the other side of the door says: "Chosen in Him before the foundation of the world...".