Depending on your definition of "main characters", the only one I can come up with is Chakotay, who entered the academy in 2344 at the age of 15, and graduated in 2348.
Honorable mentions go to Ben Sisko, who entered the academy in 2350, and so is the next most likely to have worn the red menace since we don't have a hard end date short of 2364; and Dr. Lewis Zimmerman, who graduated the academy in 2342. While Zimmerman isn't a main character, he was the model for Voyager's EMH, and was played by Bob Picardo.
Quite a few Captains and Admirals who make walk-on appearances could be expected to have been in uniform in the 2340s, but when it comes to main cast, there aren't many who were born before the early 2330s, which seems like a necessity to have been in uniform by 2349. By these means we can rule out:
- Will Riker, born 2335, admitted to Starfleet Academy 2353.
- Worf, born 2340, admitted to Starfleet Academy sometime after 2355.
- Geordi LaForge, born 2335, admitted to Starfleet Academy 2353.
- Deanna Troi, born 2336, admitted to Starfleet Academy 2355.
- Tasha Yar, born 2337, on Turkana IV until 2352.
- Jadzia Dax. Jadzia was born in 2341 (too young), and Curzon wasn't in Starfleet, so either way you slice it...
- Julian Bashir, born 2341, graduated Starfleet Medical Academy 2368.
- Kathryn Janeway, birthdate unknown, was in high school in 2359, the last time she played tennis prior to "Future's End".
- Tom Paris, attended the academy in the 2360s.
- B'Elanna Torres, born 2349.
- Harry Kim, born 2349, attended the academy in the late 2360s.
Plus all of the regulars who were never members of Starfleet in the first place (Kira, Odo, Garak, Quark, Seven, Neelix, etc.)