The majority of native speakers would use #2 (I numbered them for you). It's logical because, in general, we buy two shoes at a time so "pair of shoes" is better if the words are kept together.
However #1 is not grammatically wrong. It does, however, leave open the idea that, although you bought two new shoes, you might have chosen to buy one new shoe and one old shoe!