Not only do we not know the date, we don't even know whether he wrote the remark at all.
For all we know it might have been invented by his son Samuel, who published his father's comments. 

In his letters, Fermat never mentioned the general case at all, but quite often posed the problem of solving the cases $n=3$ and $n=4$. I am almost certain that Fermat discovered infinite descent around 1640, which means that in 1637 he did not have any chance of proving FLT for exponent 4 (let alone in general). 

In 1637, Fermat also stated the polygonal number theorem and claimed to have a proof; this is just about as unlikely as in the case of FLT -- I guess Fermat wasn't really careful in these early days. 

Let me also mention that Fermat posed FLT for $n=3$ always as a problem or as a question, and did not claim unambiguously to have a proof; my interpretation is that he did not have a proof for $n = 3$, and that he knew he did not have one. 

<b>Edit</b> Let me briefly quote two letters from Fermat:

I. <a href="http://wlym.com/~animations/fermat/">Oeuvres</a> II, 202--205, letter to Roberval Aug. 1640 Fermat claims that if $p = 4n-1$ be prime, then $p$ does not divide a sum of two squares $x^2 + y^2$ with $\gcd(x,y) = 1$. Then he writes

<em>I have to admit frankly that I have found nothing in number theory 
that has pleased me as much as the demonstration of this proposition, 
and I would be very pleased if you made the effort of finding it, if 
only for learning whether I estimate my invention more highly than it 
deserves.</em>


This looks as if Fermat had just discovered "his method" of descent.
Starting from $x^2 + y^2 = pr$ one has to show that there is a prime
$q \equiv 3 \bmod 4$ dividing $r$ which is strictly less than $p$. 

II. In his letter to Carcavi from Aug. 1659 (Oeuvres II, 431--436), Fermat writes:

<em>I then considered certain questions which, although negative, do 
not remain to receive a very great difficulty, for it will be easily 
seen that the method of applying descent is completely different from 
the preceding [questions]. Such cases include the following: 

 1.  There is no cube that can be divided into two cubes.
 2.  There is only one square number which, augmented by $2$,  
      makes a cube, namely $25$.
 3.  There are only two square numbers which, augmented by $4$, 
      make a cube, namely $4$ and $121$.
 4.  All squared powers of $2$ augmented by $1$ are prime numbers.</em>


My interpretation of this is that Fermat lists four results which he
believes can be proved using his method of descent. In my opinion 
this implies that Fermat did not have a proof of FLT for exponent $3$ 
in 1659.