The early Season 3 story with Lenwë is that his son Denethor splits off from him, leading a portion of their people into Beleriand to become the Green Elves. Once arriving in Beleriand, they settle in the lovely Ossiriand (a part of the world Treebeard waxes poetic about, so some of the ents perhaps came with Denethor? or arrive later). Then the orcs attack. The Green Elves have no metal weapons or armor. They are slaughtered, and Denethor is killed. This all happens in the first 4 episodes of Season 3, as Denethor has to be dead before Fëanor sets foot in Middle Earth and we've established that Morgoth does indeed have an army (though they won't fare so well against the well-equipped Noldor).
No doubt the migration of the Green Elves would include the Season 3 Bombadil cameo.
I agree that later seasons are a bit of an issue, but it's possible that Bombadil can travel a bit. Just because he's locked into his own land and won't leave those bounds in the 3rd Age doesn't mean he's always been that way. Perhaps his territory has shrunk, the way the Old Forest itself use to stretch all the way to Fangorn, but no longer.
If there is a season where he really, truly does not fit...we can leave out the cameo. Keep in mind that *FRAME* cameos are also an option. Season 4 will have a Bilbo-in-the-Shire-meeting-travelers frame, so having Bilbo meet Bombadil (or meet someone who met him) seems possible.