You should put down single no matter whether you are married or not since you are an NR. You cannot claim expemtion from withholding. On the contrary, your company should withhold some extra taxes because you are an NR. You should write N/R on the dotted line of 6. If you read the instructions to W-4, you'll know what I mean. The instruction is not long and is easy to understand.