Not a recruiter, but I have some expertise in this area. The applicable regulation (QR&O 1.075) is clear:
1.075 - COMMON-LAW PARTNER AND COMMON-LAW PARTNERSHIP
(1) This article applies to all regulations, orders and instructions issued to the Canadian Forces under the National Defence Act.
(2) The definitions in this paragraph apply in this article.
"common-law partner" (conjoint de fait)in relation to an officer or non-commissioned member, means a person who has been cohabiting with the member in a conjugal relationship
a. for a period of at least one year; or
b. for a period of less than one year, if the member and the person have jointly assumed the support of a child.
"common-law partnership" (union de fait)means the relationship between an officer or non-commissioned member and the common-law partner of that member.
(3) In the definition "common-law partner", child means a child or legal ward of the common-law partner or the member or both, or an individual adopted legally or in fact by the common-law partner or the member or both.
(4) For greater certainty, a common-law partnership does not end solely because the officer or non-commissioned member and the common-law partner are living separately for military reasons.
(5) When an officer or non-commissioned member has a spouse from whom the member is separated and a common-law partner, a reference to a "spouse or common-law partner" in respect of that member means the common-law partner.
(G) [P.C. 2001-1508 effective 1 September 2001]
Your child's birth certificate showing your name as a parent should suffice, especially when combined with a bank statement for a joint account (it would have both names on it). If you get electronic statements, simply print one off or ask your bank to give you one. In this case, the dates on any of these documents are irrelevant (because you have a child together). You don't need a piece of mail. The list of acceptable things proving of a common-law relationship (that the Recruiting Centre seems to be using) is only a list of examples. It is not all-inclusive, nor is it exhaustive. The person telling you that you need a piece of mail is quite frankly, wrong (although I wouldn't advise you tell them that quite so bluntly). If the "captain won't sign off on it," politely ask why, considering that the Queen's Regulations and Orders for the Canadian Forces, state that what you have is sufficient.