Since you didn't forbid looking up in (non-virtual) books - my copy of "The Global Lincoln" (one of my top favorites) says that Cuba was the first in 1937.
PS: I just checked the sources, and the note there reads "Lincoln had already appeared on a Philippines issue in 1906, when the country was under US-administration"