The Stoors lived in Eriador before Smeagol's people moved to the Gladden.
Firstly, the Hobbits had began to learn letters and languages long before Smeagol was even born, let alone before he left society. Moving on from that, it is suggested in the appendices that the Stoors had lived in Eriador before some returned to the Wilderlands.
In Appendix A we're given a bit more insight into the movements of the Stoors, and it would appear that earlier in the Third Age, they had lived in Eriador but were forced to flee due to the wars of Angmar. This would suggest that the Stoors had dealings with Men at the time, being part of the Kingdom of Arnor, allowing them to have been taught letters and languages.
It was at this time that the Stoors that had dwelt in the Angle (between Hoarwell and Loudwater) fled west and south, because of the wars, and the dread of Angmar, and because the land and clime of Eriador, especially in the east, worsened and became unfriendly. Some returned to Wilderland, and dwelt beside the Gladden, becoming a riverside people of fishers.
The Return of the King: Appendix A, "Eriador, Arnor and the Heirs of Isildur
(It is worth noting, that the Angle spoken about above is just West of Rivendell as seen in the map linked here, between the rivers Loudwater and Hoarwell)
Later in Appendix B it again suggests that the Stoors moved from Eriador back over the Misty Mountains, and therefore most likely learnt the Common Tongue before moving back over.
1356 King Argeleb I slain in battle with Rhudaur. About this time the Stoors leave the Angle, and some return to Wilderland.
The Return of the King: Appendix B, "The Third Age"
It would suggest to me that the phrasing in the prologue is not as clear as it could be, and the Appendices paint a far clearer picture that the Stoors came over the Mountains into Eriador and then split with some returning to the Wildlands. Furthermore, you seem to be confusing how old Smeagol is with how long ago these travels were taking place. The death of King Argeleb took place 1000 years before Smeagol was born.