Add new factor across multiple groups
Several possibilities. For example, to add c for existing mon-year combinations in your data frame:

rbind(df, transform(df[!duplicated(df[, 3:4]), ], col1="c", col2=NA))
#     col1 col2 mon year
# 1      a    1 Jan 2016
# 2      a    2 Feb 2016
# 3      a    3 Mar 2016
# 4      a    4 Apr 2016
# 5      b    1 Jan 2016
# 6      b    2 Feb 2016
# 7      b    3 Mar 2016
# 8      b    4 Apr 2016
# 9      a    1 Jan 2015
# 10     a    2 Feb 2015
# 11     a    3 Mar 2015
# 12     a    4 Apr 2015
# 13     b    1 Jan 2015
# 14     b    2 Feb 2015
# 15     b    3 Mar 2015
# 16     b    4 Apr 2015
# 17     c &lt;NA&gt; Jan 2016
# 21     c &lt;NA&gt; Feb 2016
# 31     c &lt;NA&gt; Mar 2016
# 41     c &lt;NA&gt; Apr 2016
# 91     c &lt;NA&gt; Jan 2015
# 101    c &lt;NA&gt; Feb 2015
# 111    c &lt;NA&gt; Mar 2015
# 121    c &lt;NA&gt; Apr 2015


To add c for all possible combinations of existing mon values and existing year values: 

rbind(df, data.frame(col1="c", col2=NA, expand.grid(mon=levels(df$mon), year=levels(df$year))))


To add c for all possible combinations of all months names and existing year values:

rbind(df, data.frame(col1="c", col2=NA, expand.grid(mon=month.abb, year=levels(df$year))))


and so on.