France, Spain, and the Knights Hospitaller often used condemned criminals as galley slaves to provide manpower to their galleys. Louis XIV (not medieval, but...) actually penned a letter to French judges asking that they sentence men to life in the galleys, rather than to death. Galley slaves go back to ancient times, too.
Another idea might be some form of Knightly Order where condemned men are used either as forced labor or as manpower, but I'm not sure how it could come about. Certainly, the hardened criminals couldn't become knights or anything like that, but could serve as basic infantry. Certainly, during the Crusades a lot of the various knight orders controlled various castles; there's also the Teutonic Knights and the Livonian Knights who were functioning states. Unsure how you could bring it about though.