Faits : A. A.a. A._ a été nommé en qualité de préposé à l'Office B._ du district de U._ par le Conseil d'Etat du canton du Valais. A la suite de la liquidation d'une succession dont il avait été chargé, le prénommé a fait l'objet d'une procédure pénale ainsi que d'une procédure disciplinaire ouverte par l'autorité de nomination. Le 20 juin 2012, le Conseil d'Etat a décidé de diminuer de moitié le traitement de l'intéressé pour une période de trois mois à compter du 1er juillet 2012. A._ a été acquitté par la Cour des affaires pénales du Tribunal pénal fédéral par jugement du 29 janvier 2013, confirmé par le Tribunal fédéral par arrêt du 22 juillet 2013 (arrêt 6B_235/ 2013). Le recours formé par A._ contre la décision du gouvernement cantonal du 20 juin 2012 a été rejeté par le Tribunal cantonal du Valais (jugement du 24 mai 2013). Saisi d'un recours du prénommé, le Tribunal fédéral a annulé le jugement cantonal ainsi que la décision du Conseil d'Etat du 20 juin 2012. Il a condamné le canton du Valais à verser une indemnité de dépens au recourant et a renvoyé la cause à la juridiction précédente pour qu'elle statue à nouveau sur la répartition des frais et dépens de la procédure cantonale (arrêt 8D_3/2013 du 22 juillet 2014, publié aux ATF 140 I 277). A.b. Par jugement du 22 août 2014, le Tribunal cantonal du Valais a notamment alloué à A._ une indemnité de dépens de 2'200 fr. à la charge du canton. A.c. Par décision du 21 janvier 2015, le Conseil d'Etat a constaté que l'arrêt du Tribunal fédéral du 22 juillet 2014 (ATF 140 I 277, ci-dessus mentionné) avait éteint la procédure disciplinaire ouverte à l'encontre de A._, et il a statué sur le traitement auquel celui-ci avait droit depuis le 1er janvier 2010. B. B.a. Par acte du 25 février 2015, A._ a recouru devant le Tribunal cantonal du Valais en concluant à l'annulation de la décision du 21 janvier 2015 et au renvoi de la cause au Conseil d'Etat. Il faisait valoir que depuis le 25 août 2014, il avait eu des discussions avec les services de la conseillère d'Etat, et cette dernière en personne, au sujet notamment des frais d'avocat qu'il avait encourus dans les procédures engagées à son endroit. Préalablement, le 20 février 2015, A._ avait saisi la conseillère d'Etat d'une requête tendant en particulier à ce que le gouvernement cantonal lui accorde une indemnisation pour ces frais. Au vu de la réponse (du 2 mars 2015) de celle-ci selon laquelle sa requête faisait l'objet d'un examen et le Conseil d'Etat statuerait sur les frais d'avocat en cause, l'intéressé a proposé la suspension de la procédure. Consulté par le Tribunal cantonal, le Conseil d'Etat a indiqué, le 13 juillet 2015, qu'il entendait laisser la cour cantonale trancher la question des frais d'avocat. Dans sa détermination du 18 novembre 2015 sur le recours de A._, le gouvernement cantonal a précisé que sa décision du 21 janvier 2015 comportait la renonciation à attribuer à l'intéressé une indemnité pour ses frais de défense. Par jugement du 18 décembre 2015, la cour cantonale a rejeté le recours. B.b. Statuant le 17 août 2016, la Ire Cour de droit social du Tribunal fédéral a déclaré irrecevable le recours constitutionnel subsidiaire interjeté par A._, mais admis son recours en matière de droit public. Elle a annulé l'arrêt cantonal du 18 décembre 2015 et renvoyé la cause à la cour cantonale pour qu'elle rende une nouvelle décision au sens des considérants (arrêt 8C_109/2016). Statuant à nouveau le 20 octobre 2016, le Tribunal cantonal du Valais a derechef rejeté le recours de A._. C. A._ interjette un recours en matière de droit public. Sous suite de frais et dépens, il conclut à la réforme (ou à l'annulation) du jugement cantonal en ce sens que la décision du Conseil d'Etat du 21 janvier 2015 est annulée et le dossier renvoyé à ce dernier pour qu'il statue sur sa demande d'indemnisation. Le Conseil d'Etat a renoncé à présenter une réponse, tout en concluant au rejet du recours.