I don't see why not. I do it all the time making corned venison and pastrami. Corning it is actual the only thing I've found to do with meat that has a little freezerburn funk and I can't detect it at all. Even sausages I can still pick it up a little.
Can't remember the last time I brined something that wasn't frozen. Freezing results in the cells bursting and a less moist cut as compared to fresh, but the brine is going to penetrate the meat as the salt tries to reach equilibrium. The brine won't penetrate the meat until it is thawed.