C (gcc), 270 250 bytes
char*s[]={"Mon","Tues","Wednes","Thurs","Fri","sth"};l(y){return y/4-y/100+y/400;}
f(m,y){int d,p=l(y);y-=d=m<3;d=6+y+p+(31*(m+=12*d-2))/12;
d+=y=31-(12652612>>(m*2-2)&3)+(m>11&p-l(y));d%=7;y-=p=d&d/4*3;
printf("%sday %d%.2s\n",s[d-p],y,s[5]+(y<31));}
Doing it the hard way - a bunch of mod 7 math to count extra days since the first Monday of Year 0.
p=l(y) returns the number of leap years since 0.
d=m<3 is true for Feb and March
y-=d...m+=12*d-2 sets m to the month, where Mar is 1 and Jan and Feb are 11 and 12 of the prior year.
d=6+y+p+31*m/12 sets d to the number of extra days between the first Monday in year 0 and the last day of the prior month. (the 31*m/12 gives the correct pattern of +3s and +2s)
(m>11&p-l(y) is 1 if it's February of a leap year
12652612 is "31-days" for each month encoded in 2 bits, so
y=31-(12652612>>(m*2-2)&3)+... sets y to the last day in the query month.
d+=y...;d%=7 gets the day of the week (0==Mon) for the query.
p=d&d/4*3 sets p to the days needed to truncates Sat/Sun to Fri (4)
y-=p fixes the last day of the month
s[d-p] is the day string,
2 characters from s[5]+(y<31) is "st" or "th"