Правомерно ли поступает прокуратура в данном случае?

В вашем случае это не обратная сила закона. Но увольнение возможно если у работодателя отсутствует какая либо другая работа. Требования прокурора законны из следующего:

Согласно абз. 4 ст. 331 ТК РФ к педагогической деятельности не допускаются лица, имеющие или имевшие судимость, подвергающиеся или подвергавшиеся уголовному преследованию (за исключением лиц, уголовное преследование в отношении которых прекращено по реабилитирующим основаниям) за преступления против жизни и здоровья (за исключением незаконного помещения в психиатрический стационар, клеветы и оскорбления), половой неприкосновенности и половой свободы личности, против семьи и несовершеннолетних, здоровья населения и общественной нравственности, а также против общественной безопасности.

В соответствии с главой 16 Уголовного кодекса Российской Федерации преступление, предусмотренное статьей 112 УК РФ, относится к преступлениям против жизни и здоровья.

В соответствии с п. 13 ч. 1 ст. 83 ТК РФ трудовой договор подлежит прекращению по обстоятельствам, не зависящим от воли сторон: в случае возникновение установленных настоящим Кодексом, иным федеральным законом и исключающих возможность исполнения работником обязанностей по трудовому договору ограничений на занятие определенными видами трудовой деятельности.

Часть 2 ст. 83 ТК РФ предусматривает, что прекращение трудового договора по п. 13 ч. 1 ст. 83 ТК РФ допускается, если невозможно перевести работника с его письменного согласия на другую имеющуюся у работодателя работу которую работник может выполнять с учетом его состояния здоровья.