Faits: A. A.a Par contrat de travail de droit privé du 13 septembre 2007, le Département de la gestion du territoire du canton de Neuchâtel a engagé A._ en qualité d'aide-concierge auxiliaire à temps partiel au service de l'intendance des bâtiments de X._, pour la période du 24 septembre au 31 décembre 2007. A la suite du transfert du service des bâtiments (respectivement du personnel de conciergerie des bâtiments de X._) au sein de l'établissement X._, A._ a été engagé à partir du 1er janvier 2008 en qualité d'aide-concierge à temps complet, à titre provisoire, au Bureau de l'intendance des bâtiments de X._. Par courrier du 13 juillet 2009, faisant suite à un entretien d'évaluation ayant eu lieu le 25 juin 2009, A._ a été invité par le responsable du service intendance et logistique à améliorer la qualité de ses prestations et à faire preuve de plus de dynamisme et d'engagement dans l'accomplissement de ses activités. Un nouveau point de la situation a été fait le 18 septembre 2009, à l'issue duquel A._ s'est vu informé, dans un courrier du 24 septembre 2009, que les progrès constatés restaient insuffisants et qu'il était invité à améliorer ses prestations. Par lettre du 2 octobre 2009, le Directeur administratif de X._ a annoncé à A._ qu'une résiliation des rapports de travail durant la période provisoire était envisagée et qu'un délai de 15 jours lui était accordé pour s'exprimer par écrit. Dans le délai imparti, A._ a déposé ses observations, contestant en particulier le fait que X._ avait laissé s'écouler une période de 18 mois avant de lui reprocher que son travail n'était pas satisfaisant. Par décision du 13 novembre 2009, X._ a résilié les rapports de service de A._ avec effet au 31 janvier 2010, en raison de l'insuffisance de ses prestations. A.b A._ a interjeté un recours contre cette décision devant le Département de l'éducation, de la culture et des sports (ci-après: le DECS). Par décision du 9 juillet 2010, le DECS a rejeté le recours. B. B.a A._ ayant recouru contre cette décision, la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel l'a débouté par arrêt du 17 janvier 2011. Saisi d'un recours de l'intéressé, le Tribunal fédéral l'a admis, par arrêt du 12 décembre 2011 (8C_144/2011), en ce sens qu'il a annulé le jugement cantonal et renvoyé la cause à la juridiction cantonale pour nouvelle décision dans le sens des considérants (selon lesquels le jugement entrepris souffrait d'un défaut de motivation). B.b Reprenant l'instruction de la cause, la Cour de droit public du Tribunal cantonal neuchâtelois a invité X._ à produire le dossier du transfert du personnel du Service des bâtiments de l'Etat. Elle a par ailleurs requis de celui-ci de fournir le dossier de A._, ainsi que tous les renseignements utiles quant à l'engagement de celui-ci du 24 septembre au 31 décembre 2007 et sur le régime auquel était soumis les différents collaborateurs transférés à X._ dès le 1er janvier 2008. Une fois les documents sollicités versés à la procédure, les parties ont pu se déterminer à leur sujet. Statuant le 30 avril 2012, le Tribunal cantonal a derechef rejeté le recours. C. Agissant par la voie du recours en matière de droit public contre ce jugement, A._ demande au Tribunal fédéral de l'annuler, de même que la décision du DECS du 9 juillet 2010 et celle de X._ du 13 novembre 2009. X._ conclut au rejet du recours.