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.

Considérant en droit:
1. 1.1 Le jugement entrepris a été rendu en matière de rapports de travail de droit public au sens de l'art. 83 let. g LTF. Dans la mesure où la contestation porte sur l'annulation d'une décision de résiliation des rapports de travail, il s'agit d'une contestation de nature pécuniaire, de sorte que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération (voir par exemple les arrêts 8C_907/2010 du 8 juillet 2011 consid. 1 et 8C_170/2009 du 25 août 2009 consid. 1.1). La valeur litigieuse atteint par ailleurs le seuil de 15'000 fr. (art. 51 al. 2 et 85 al. 1 let. b LTF). La voie du recours en matière de droit public selon les <ref-law> est donc ouverte pour contester la décision attaquée.
2. Le litige porte sur la résiliation des rapports de travail du recourant, singulièrement sur les dispositions légales applicables à cette dernière.
3. Sous le titre marginal "Contrats de droit privé", l'art. 7 al. 1 de la loi neuchâteloise du 28 juin 1995 sur le statut de la fonction publique (LSt; RSN 152.510) prévoit ceci:
Le Conseil d'Etat ou l'autorité qu'il désigne à cet effet peut, à titre exceptionnel, engager du personnel par contrat de droit privé, notamment pour l'exécution de tâches spéciales, ou de durée limitée, ou encore pour assurer le remplacement temporaire d'un titulaire de fonction publique.
Quant à l'art. 8 LSt, intitulé "Définition", il a la teneur suivante:
Est titulaire de fonction publique au sens de la présente loi toute personne faisant l'objet d'un engagement provisoire ou d'une nomination à temps complet ou à temps partiel.
Sous le titre "Engagement provisoire", l'art. 12 LSt dispose ce qui suit:
1La nomination est précédée d'un engagement provisoire d'une durée de deux ans qui constitue la période probatoire.
2La période probatoire peut être abrégée ou supprimée lorsque l'autorité de nomination estime qu'elle ne se justifie pas.
3Durant la période probatoire, chaque partie peut signifier son congé à l'autre moyennant un avertissement donné par écrit au moins deux mois à l'avance pour la fin d'un mois. Le congé ne doit pas être abusif, au sens de l'art. 336 du code des obligations.
Sous le chapitre 3, "Cessation des rapports de service", l'art. 37 LSt en énumère les "Causes"; la let. f de cette disposition prévoit que:
Les rapports de service des titulaires de fonctions publiques prennent fin par le renvoi pour de justes motifs ou pour raisons graves.
Les conditions du renvoi pour justes motifs ou pour raisons graves sont définies aux art. 45 ss LSt.
4. 4.1 La juridiction cantonale s'est fondée sur l'art. 7 al. 1 LSt pour retenir que l'engagement initial du recourant par un contrat de droit privé (du 13 septembre 2007) était conforme au droit. Le recourant avait été engagé par le Service des bâtiments de l'Etat (au sein du Département de la gestion du territoire du canton de Neuchâtel) pour une durée limitée (du 24 septembre au 31 décembre 2007) afin de remplacer une personne démissionnaire. A cette époque, X._ avait obtenu que les concierges affectés au nettoyage de ses bâtiments lui fussent attribués dès le 1er janvier 2008; ceux-ci dépendaient du point de vue administratif de X._ depuis le 1er juillet 2007 déjà, mais financièrement du Service des bâtiments de l'Etat jusqu'au 31 décembre 2007. Pour cette raison, le recourant avait été engagé pour une période limitée et par un contrat de droit privé, afin de laisser à X._ la faculté d'engager son propre personnel dès le 1er janvier 2008.
Aussi, de l'avis des premiers juges, le refus de prendre en compte les trois mois que le recourant avait effectués auprès du Service des bâtiments dans la période probatoire de deux ans (au sens de l'art. 12 al. 1 LSt) ne contrevenait-il pas aux dispositions de la LSt. La nomination du recourant en qualité d'aide-concierge auprès de X._ ne pouvait intervenir qu'à partir du 1er janvier 2010, de sorte que la résiliation de ses rapports de service devait respecter l'art. 12 al. 3 LSt, à l'exclusion des art. 37 ss LSt. Dès lors que les conditions de l'art. 12 al. 3 LSt avaient été réalisées - le recourant n'avait pas rempli à satisfaction les exigences de la fonction et avait été averti de l'intention de son employeur de résilier les rapports de service -, la décision de résiliation du 13 novembre 2009 n'était pas critiquable.
4.2 Se plaignant d'une violation des art. 7, 9, 12 et 45 LSt ayant conduit la juridiction cantonale à retenir une solution arbitraire, le recourant lui reproche en substance d'avoir nié que les mois de travail qu'il avait effectués à l'Etat "sont passés à X._ dès le moment où il y a été transféré". Dès lors que l'X._ avait évoqué son "transfert" et reconnu que sa date d'entrée en fonction avait été fixée au 24 septembre 2007, et que tous les concierges occupés à l'entretien des bâtiments de X._ dépendaient administrativement de l'intimée depuis le 1er juillet 2007, le second contrat devait être considéré comme la continuation du premier, les deux engagements constituant des "contrats en chaîne" dont le début devait être situé au 24 septembre 2007. Selon le recourant, son engagement initial n'était par ailleurs pas conforme au droit, puisque les conditions de l'art. 7 al. 1 LSt n'étaient pas réalisées, un engagement par l'Etat par le biais d'un contrat de droit privé revêtant un caractère exceptionnel comme le soulignait la doctrine. Il avait, de plus, postulé pour un emploi de durée indéterminée et reçu automatiquement un nouveau contrat daté du 20 décembre 2007, sans que X._ n'eût procédé à une démarche particulière d'engagement. Le recourant soutient qu'il aurait par conséquent dû être nommé automatiquement à partir de deux ans (à savoir dès le 24 septembre 2009) et que le licenciement ne pouvait être prononcé en application de l'art. 12 al. 3 LSt, mais aurait dû respecter la procédure des art. 45 ss LSt. A défaut, la décision de résiliation des rapports de service devait être annulée.
5. 5.1 Le recours en matière de droit public devant le Tribunal fédéral ne peut pas être interjeté pour violation du droit cantonal en tant que tel, mais il est possible de faire valoir qu'une mauvaise application du droit cantonal constitue une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à d'autres droits constitutionnels (<ref-ruling> consid. 4.3 p. 521 s.; <ref-ruling> consid. 2.3 p. 466). Selon la jurisprudence, une décision est arbitraire au sens de l'art. 9 Cst. lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité (<ref-ruling> consid. 2.1 p. 211; <ref-ruling> consid. 2 p. 61). S'agissant de la manière dont le droit cantonal a été appliqué, il ne faut pas confondre arbitraire et violation de la loi: une violation doit être manifeste et reconnue d'emblée pour être considérée comme arbitraire. Le Tribunal fédéral n'a pas à examiner quelle est l'interprétation correcte que l'autorité cantonale aurait dû donner des dispositions applicables; il doit uniquement dire si l'interprétation qui a été opérée est défendable. Il n'y a pas arbitraire du seul fait qu'une autre solution paraît également concevable, voire préférable (<ref-ruling> consid. 5.1 p. 17; <ref-ruling> consid. 2.1 p. 219).
5.2 Conformément à l'art. 12 al. 3 LSt, durant la période probatoire, chaque partie a la possibilité de résilier les rapports de travail moyennant un avertissement écrit, donné deux mois à l'avance pour la fin d'un mois; est réservé le congé abusif au sens de l'<ref-law>. Il découle par ailleurs de l'art. 12 al. 1 LSt, selon lequel "la nomination est précédée d'un engagement provisoire d'une durée de deux ans qui constitue la période probatoire", que la période provisoire débute au moment de l'engagement provisoire et comporte une durée de deux ans (sous réserve d'un abrégement ou d'une suppression au sens de l'art. 12 al. 2 LSt).
5.3 Il ressort des faits établis par la juridiction cantonale que le recourant a été engagé par le Département de la gestion du territoire du canton de Neuchâtel en qualité d'aide-concierge auxiliaire à temps partiel pour une durée déterminée, du 24 septembre au 31 décembre 2007, afin de remplacer une personne démissionnaire; cet engagement a fait l'objet d'un contrat de droit privé du 13 septembre 2007. Le 20 décembre suivant, X._ a confirmé au recourant son engagement à partir du 1er janvier 2008 en qualité d'aide-concierge, à temps complet et à titre provisoire, au Bureau de l'intendance des bâtiments de X._, les dispositions de la LSt (dont un exemplaire était joint au courrier) faisant partie intégrante du contrat d'engagement. Le recourant n'a alors pas réagi et ne s'est pas opposé aux conditions d'engagement de l'intimée, en particulier quant à la date du début des rapports de service (au 1er janvier 2008).
Sous l'angle des rapports de service entre le recourant et l'intimée, l'engagement provisoire de celui-ci a dès lors débuté le 1er janvier 2008. La décision de résiliation du 13 novembre 2009, qui a été précédée d'un avertissement et rendue moins de deux ans après le début de l'engagement provisoire ("durant la période provisoire") était donc en principe soumise à la procédure et aux exigences prévues par l'art. 12 LSt.
5.4 Il reste à examiner si, en retenant que la période d'activité (d'un peu plus de trois mois) antérieure au 1er janvier 2008 ne devait pas être considérée comme un rapport de droit public, la juridiction cantonale a fait une interprétation du droit cantonal qui doit être qualifiée d'arbitraire.
5.4.1 Sans se prononcer sur le point de savoir si les cantons peuvent de manière générale soumettre les rapports de travail qui les lient à des collaborateurs au droit privé, le Tribunal fédéral a indiqué qu'un tel engagement de droit privé suppose en tous les cas qu'il trouve un fondement dans une réglementation cantonale claire et sans équivoque, et qu'il ne soit pas exclu par le droit applicable (<ref-ruling> consid. 3 p. 217; cf. aussi arrêt 2P.18/2006 du 19 mai 2006 consid. 2.3).
Une telle réglementation existe en droit cantonal neuchâtelois: l'art. 7 al. 1 LSt prévoit la possibilité pour le Conseil d'Etat ou l'autorité désignée à cet effet d'engager à titre exceptionnel du personnel par contrat de droit privé. Trois situations sont envisagées à titre d'exemples ("notamment"), à savoir l'exécution de tâches spéciales, l'exécution de tâches de durée limitée ou le remplacement temporaire d'un titulaire de fonction publique.
5.4.2 Selon les constatations de fait de la juridiction cantonale, à l'époque de l'engagement du recourant par le Département de la gestion du territoire du canton de Neuchâtel, il avait été convenu que les concierges affectés au nettoyage des bâtiments de X._ lui seraient attribués dès le 1er janvier 2008. Jusqu'au 31 décembre 2007, ceux-ci dépendaient toutefois encore financièrement du Service des bâtiment, alors qu'ils relevaient déjà de X._ du point de vue administratif.
Les premiers juges ont considéré que ces circonstances justifiaient que le Département de la gestion du territoire du canton de Neuchâtel engageât le recourant pour une durée déterminée par un contrat de droit privé au sens de l'art. 7 al. 1 LSt. Quoi qu'en dise le recourant, une telle interprétation n'apparaît pas insoutenable. On peut en effet concevoir que le Service des bâtiments de l'Etat, qui cherchait à remplacer un concierge démissionnaire affecté à l'entretien des bâtiments de X._ peu de temps avant que le poste en tant que tel soit transféré à celle-ci, conclue avec le recourant un contrat de durée limitée soumis au droit privé. Du point de vue du Département de la gestion du territoire du canton de Neuchâtel, l'engagement du recourant ne pouvait prendre la forme que de rapports de travail de durée limitée soumis au droit privé, puisque le poste de concierge affecté aux bâtiments de X._ ne dépendait plus du Département dès le 1er janvier 2008, mais d'une autre entité de droit public, et qu'il ne pouvait donc assurer au recourant un poste à long terme. S'il est vrai que l'engagement du recourant n'avait pas trait à des tâches spéciales ou de durée limitée - les travaux de conciergerie ont perduré au-delà du 31 décembre 2007 -, ni ne constituait un remplacement temporaire, l'autorité qui souhaitait le recruter ne pouvait cependant pas s'obliger à le maintenir à un poste dont la responsabilité lui échappait près de trois mois après la conclusion du contrat de travail.
5.4.3 Dans ce contexte, il importe peu que le recourant ait postulé pour une activité de durée indéterminée comme il le fait valoir, puisque le contrat de travail du 13 septembre 2007 indiquait précisément la durée de son engagement, avec un terme fixé au 31 décembre 2007, auquel il a alors entièrement souscrit.
Le point de savoir de quelle collectivité publique le recourant a reçu des instructions pendant cette période n'est pas non plus déterminant, contrairement à ce qu'il fait valoir, puisque son employeur était clairement le Service des bâtiments de l'Etat, respectivement le Département de la gestion du territoire, qui lui versait son salaire. Le recourant fait par ailleurs une lecture erronée des déterminations de l'intimée, lorsqu'il en tire la conclusion qu'elle aurait reconnu que sa date d'entrée en fonction correspondait au 24 septembre 2007. X._ a en effet indiqué que dans son système informatique la date d'entrée en fonction de tous les concierges qui avaient bénéficié d'un engagement provisoire auprès d'elle à partir du 1er janvier 2008 était "celle de la première date d'entrée en fonction au service de l'Etat", mais que la période d'engagement provisoire avait en revanche commencé au 1er janvier 2008 "sans qu'il ne soit tenu compte des années passées auparavant au service de l'Etat" (observations du 15 février 2012). Précisant qu'elle avait engagé provisoirement pour une durée de deux ans à partir du 1er janvier 2008 toutes les personnes qui n'étaient pas au bénéfice d'une nomination par le Conseil d'Etat au 31 décembre 2007, l'intimée a donc confirmé que le recourant n'avait pas bénéficié de conditions moins avantageuses que les autres concierges concernés à l'époque et que le début de la période probatoire avait clairement été fixée au 1er janvier 2008.
Enfin, on ne voit pas quel argument le recourant entend tirer de l'absence d'entretien d'embauche à la fin de l'année 2007. Il s'agit là d'une modalité d'engagement qui ne paraissait pas indispensable, puisque l'intimée n'ignorait manifestement pas quelles personnes s'occupaient de l'entretien de ses bâtiments et était en mesure de se rendre directement compte de la qualité de leur travail. En tant que le recourant mentionne encore l'<ref-law> sur le transfert des rapports de travail, sans expliquer en vertu de quelles règles cette disposition de droit privé trouverait application en l'espèce, son argument ne répond pas aux exigences minimales de motivation et n'a pas à être examiné plus avant. Celles-ci lui imposent d'indiquer concrètement quels éléments précis permettraient de considérer que la juridiction cantonale aurait de manière arbitraire manqué d'appliquer la disposition dont elle se prévaut (qui devrait être appliquée à titre subsidiaire comme droit cantonal supplétif).
5.4.4 Il découle de ce qui précède que l'interprétation du droit cantonal qui a été opérée par la juridiction cantonale apparaît défendable, l'argumentation du recourant n'étant pas susceptible d'en démontrer le caractère insoutenable.
5.5 Pour le reste, le recourant ne soutient pas (et ne démontre donc pas non plus) qu'il avait reçu de l'Etat de Neuchâtel une quelconque assurance que les rapports de travail (de droit privé) allaient être suivis d'un engagement provisoire au service de X._ dont le début aurait rétroagi au 24 septembre 2007. Peu importait dès lors de savoir "ce qu'il était prévu que devienne le recourant à partir du 1er janvier 2008", comme l'invoque celui-ci en soutenant que les deux témoins dont il avait sollicité l'audition en instance cantonale étaient à même de donner des informations utiles et propres à influer sur l'issue du litige. Dès lors que la juridiction cantonale a complété son instruction et établi les faits relatifs aux circonstances dans lesquelles le recourant avait été engagé par l'Etat de Neuchâtel, puis par l'intimée, il n'était pas indispensable qu'elle entende des témoins à ce sujet. Le grief tiré de la violation du droit d'être entendu tombe par conséquent à faux.
6. Cela étant, le recourant ne remet pas en cause les considérations des premiers juges quant au bien-fondé de la résiliation des rapports de service à la lumière des insuffisances qualitative et quantitative de son travail. Il n'y a dès lors pas lieu de s'en écarter.
Le recours se révèle en conséquence mal fondé.
7. Vu l'issue du litige, le recourant, qui succombe, supportera les frais de justice (<ref-law>). L'intimée n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public.
Lucerne, le 14 février 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente: Leuzinger
La Greffière: Moser-Szeless