You are most likely first cousins.
You are correct to say that first cousins on average share about 850 cM, but due to the randomness of genetic recombination, the range of the amount of DNA inherited from a common ancestor can vary immensely. It's a bell curve – some first cousins will share more DNA than other first cousins. A match of 1246.5 cM is not inconsistent with a first cousin match.
According to the Shared cM Project, the range of shared cM for a first cousin relationship is 533 to 1379 cM. See the latest report (25 Jun 2016) for the most recent data. There is this histogram of cM shared for first cousins:

As you can see from this histogram, your relationship with cousin is right at the top end of the range. Only 9 out of 869 first cousins (less than 1%) share more than 1222 cM. But it's not impossible.
You will note that 1246 cM does not fall in the range for any other relationship in the data from the Shared cM Project, making first cousin most likely. A possible explanation for sharing more than average DNA would be that you are first cousins, but you also share another more distant relationship. For example, you might be first cousins as well as second cousins once removed on another line. I think this is the most likely scenario – you are second cousins once removed (2C1R) as you predicted, but you also share a closer relationship as first cousins.
According to the Shared cM Project data, the amount of autosomal DNA shared by 2C1R is anything from 0 to 325 cM. The average amount shared is 129 cM. Based on your results I think it is extremely unlikely that you could share 1246 cM and only be 2C1R.
The fact that you share no X-DNA is expected. Your cousin only inherited an X-chromosome from his mother, and since you are related via his father's line, you should not share any X-DNA.
To work out how you are related I would look closely at each of your grandparents and see if you can find a possibility (considering time, place) that you are first cousins. Focus on your cousin's father's side, since you share no X-DNA therefore are unlikely to be related by his mother. You could be related as first cousins by either your mother or father's lines. Consider whether any family adoptions may have occurred. I have a case in my family where an uncle and aunt adopted their nephew, and it's possible something like that could have happened here.