You can use nl to number the lines (that's the program purpose :). But you need to extract the first week in the month from somewhere. It can be done from ncal itself:
$ ncal -w 2 2012 | tail -1 | awk '{print $1}'
5
We insert this as a parameter to nl's option -v (starting line number), and tell it to only number lines with numbers or spaces.
$ cal 2 2012 | nl -bp'^[0-9 ]\+$' -w2 -s' ' -v$(ncal -w 2 2012 | tail -1 | awk '{print $1}')
February 2012
Su Mo Tu We Th Fr Sa
5 1 2 3 4
6 5 6 7 8 9 10 11
7 12 13 14 15 16 17 18
8 19 20 21 22 23 24 25
9 26 27 28 29
This is all awfully fragile though. Anyway, if you aren't going to need cal's more advanced options, it will work. You can put it in a file and replace "$@" where I put 2 2012.
EDIT: But this is WRONG! I just noticed that the first week in January can have number 52 or 53! So we just either have to make an exception for January, or just extract all the week numbers from ncal and apply them to the output of cal.
This is the solution I thought originally, but I thought (erroneously) I would simplify it using nl. It uses paste, which merges files side-by-side. Since there isn't any file, we have to use the bashism <(...); that's what I was trying to avoid.
Our first "file" will be a list of the week numbers, with two empty lines at the beginning:
$ printf ' \n \n' && printf '%2d \n' $(ncal -w 1 2011 | tail -1)
52
1
2
3
4
5
The second one, just the output of cal. All together, as parameters to paste:
$ paste -d' ' <(printf ' \n \n' && printf '%2d \n' $(ncal -w 1 2011 | tail -1)) <(cal 1 2011)
January 2011
Su Mo Tu We Th Fr Sa
52 1
1 2 3 4 5 6 7 8
2 9 10 11 12 13 14 15
3 16 17 18 19 20 21 22
4 23 24 25 26 27 28 29
5 30 31
Much messier and incompatible that the other one. En fin...