I have gone through few articles but I am not convinced on what should I do with these. I know from business standpoint it might be good to consider fraudulent transactions happening from unknown locations. But I don't know how to use this in my data as dummy encoding might not be good solution.
Why do you think that
... as dummy encoding might not be good solution
? If it is because of memory issues, find some software that is using sparse matrices, like glmnet. Since there are very many different zip codes, have a look at Principled way of collapsing categorical variables with many levels? and the suggestions there. I would try out the fused lasso.
It is also possible that for your application, some domain knowledge would be helpful for feature construction.