Faits:
A. F._, né en 1963, bénéficie d'une aide sociale de la commune X._, où il est domicilié, depuis le 29 septembre 1998. Le 28 avril 2008, cette dernière a décidé de réduire le montant de l'aide sociale en supprimant le forfait d'intégration de 100 fr. qu'elle lui allouait et en diminuant de 15 % (144 fr.) le forfait d'entretien. Il s'agissait de sanctionner un défaut de collaboration de l'intéressé à la recherche d'un emploi, après plusieurs avertissements précédents. Ces pénalités étaient prononcées pour une durée de six mois et prendraient effet le 1er mai 2008. F._ a recouru contre cette décision devant le Conseil d'Etat du canton du Valais (ci-après : le Conseil d'Etat).
Le 11 juin 2008, alors que la procédure devant le Conseil d'Etat était pendante, la commune X._ a décidé de réduire à 550 fr. le forfait mensuel d'entretien alloué à F._, pour une période de trois mois dès le 1er juin 2008. Le 18 juin suivant, le Conseil d'Etat a rejeté le recours interjeté contre la décision du 28 avril 2008.
B. F._ a recouru devant le Tribunal cantonal valaisan contre la décision du Conseil d'Etat. La juridiction cantonale a déclaré le recours partiellement irrecevable et l'a rejeté pour le surplus, par jugement du 16 janvier 2009.
C. F._ interjette un recours en matière de droit public contre ce jugement. Il conclut à la constatation d'une violation des art. 6 par. 1 et 7 par. 1 CEDH par la juridiction cantonale, ainsi que de diverses autres normes de droit international, ou de droit fédéral, cantonal ou communal. Il demande, en outre, sa « réintégration à l'Ecole Y._ pour le semestre d'étude 2009-2010 » et la condamnation de la commune X._ au paiement de 4654 fr. d'arriérés de prestations. Le recourant demande en outre au Tribunal fédéral de tenir une audience publique pour l'instance fédérale et l'octroi de l'effet suspensif au recours. L'intimé conclut au rejet du recours.

Considérant en droit:
1. Le recourant soulève deux griefs d'ordre formel à l'encontre de la procédure suivie en instance cantonale. Les deux concernent une violation du droit d'être entendu garanti par l'art. 6 par. 1 CEDH : d'une part, la juridiction cantonale n'aurait pas suffisamment motivé le jugement entrepris sur la question de la violation de diverses normes de droit international ainsi que de dispositions de droit cantonal et communal par l'autorité intimée; d'autre part, elle aurait tenu une audience publique le 17 décembre 2008, en l'absence du recourant et sans l'avoir convoqué valablement.
2. Aux termes de l'art. 42 al. 1 et 2, 1ère phrase, LTF, le recours doit être rédigé dans une langue officielle, indiquer les conclusions, les motifs et les moyens de preuve, et être signé. Les motifs doivent indiquer succinctement en quoi l'acte attaqué viole le droit. Par ailleurs, si le Tribunal applique le droit d'office, il n'examine la violation de droits fondamentaux ainsi que celle de dispositions de droit cantonal et intercantonal que si ce grief a été invoqué et motivé (art. 106 al. 1 et 2 LTF).
En l'occurrence, le grief relatif à une motivation insuffisante du jugement entrepris ne répond pas à ces exigences. Le recourant se borne à citer pêle-mêle des dispositions de conventions internationales, de droit cantonal et de droit communal en précisant que leur violation par l'intimée n'a pas fait l'objet d'une discussion par les premiers juges. Il n'expose toutefois pas quelle serait leur pertinence en l'espèce, ni ne précise quand et comment il les aurait invoquées en instance cantonale. Il n'y a donc pas lieu d'entrer en matière sur le grief de motivation insuffisante du jugement entrepris.
3. 3.1 L'art. 6 par. 1 CEDH garantit notamment, à toute personne qui soumet à un tribunal une «contestation sur des droits et obligations de caractère civil», le droit à ce que sa cause soit entendue publiquement. Dans le contentieux devant l'autorité judiciaire de première instance, cela implique en principe le droit d'exiger du tribunal qu'il tienne une audience de débats publique. Il en va différemment en deuxième instance, dans des cas où l'autorité de recours dispose d'un pouvoir d'examen limité et où la procédure n'a pas pour objet d'élucider des faits non encore établis (<ref-ruling> consid. 3 p. 54; <ref-ruling> consid. 3 p. 7; arrêt du Tribunal fédéral des assurances B 58/02 du 25 octobre 2002 consid. 5, in RSAS 2004 p. 150).
3.2 Le «caractère civil» d'un droit est une notion autonome de la Convention européenne; sont décisifs le contenu matériel du droit en cause et les effets que lui confère la législation interne de l'Etat concerné. Ainsi, l'art. 6 par. 1 CEDH ne concerne pas seulement les contestations de droit privé au sens étroit - c'est-à-dire celles qui surgissent entre des particuliers, ou entre un particulier et l'Etat agissant au même titre qu'une personne privée -, mais aussi les actes administratifs adoptés par une autorité dans l'exercice de la puissance publique, pour autant qu'ils produisent un effet déterminant sur des droits de caractère civil (<ref-ruling> consid. 6.2 p. 238; <ref-ruling> consid. 2.4 sv. p. 469 sv.; <ref-ruling> consid. 5.1 p. 394). L'art. 6 par. 1 CEDH ne vise pas à créer de nouveaux droits matériels qui n'ont pas de fondement légal dans l'Etat concerné, mais à accorder une protection procédurale aux droits reconnus par l'ordre juridique interne. Il régit uniquement les contestations relatives à des droits (de caractère civil) que l'on peut dire, au moins de manière défendable, reconnus en droit interne; il n'assure par lui-même aux «droits et obligations» (de caractère civil) aucun contenu matériel déterminé dans l'ordre juridique des Etats contractants (<ref-ruling> consid. 7a p. 215 sv. et les références).
3.3 La notion de contestation relative à des «droits et obligations à caractère civil» comprend notamment les litiges relatifs à des prestations d'assurances sociales ou au paiement de cotisations aux assurances sociales en Suisse (<ref-ruling> consid. 3.3 p. 70; <ref-ruling> consid. 2a p. 50). Elle comprend, en outre, les litiges relatifs à des prestations d'aide sociale, pour autant que la législation interne de l'Etat concerné y confère un droit. Le fait que les prestations d'aide sociale sont entièrement financées par l'Etat et non par le paiement de cotisations n'est pas déterminant. Dès lors que le justiciable, atteint dans ses moyens d'existence, invoque un intérêt patrimonial et n'est pas concerné dans ses rapports avec l'administration en tant que telle, usant de prérogatives discrétionnaires, la contestation en matière d'aide sociale porte sur un droit à caractère civil au sens de l'art. 6 par. 1 CEDH (arrêts de la Cour européenne des droits de l'homme Schuler-Zgraggen contre Suisse du 24 juin 1993, Série A vol. 263 § 46 et Salesi contre Italie du 26 février 1993, Série A vol. 257 § 17 ss; cf. également les arrêts du Tribunal fédéral 2P.103/2001 du 6 novembre 2001 consid. 3; 1A.120/2004 du 19 octobre 2004 consid. 2.4; 2D_77/2008 du 16 mars 2009 consid. 5.4). Le seul fait que l'administration dispose d'un certain pouvoir d'appréciation pour l'octroi des prestations n'exclut pas l'application de cette disposition. Il est en revanche déterminant que l'autorité statue sur la base de règles légales précises et qu'elle ne soit pas entièrement libre d'allouer ou non l'appui demandé (arrêts de la Cour européenne des droits de l'homme H. contre Belgique du 30 novembre 1987, Série A vol. 127 § 43, Mats Jacobsson contre Suède du 28 juin 1990, Série A vol. 180 § 32; Lombardo contre Italie du 26 novembre 1992, Série A vol. 249 § 17; voir également arrêt du Tribunal fédéral des assurances K 21/03 consid. 3.3 non publié in <ref-ruling>; ATF <ref-ruling> consid. 5.1 p. 394; <ref-ruling> consid. 6b sv. p. 180 sv.).
3.4 En l'occurrence, le litige tranché par la juridiction cantonale portait sur le droit du recourant à une aide financière au titre de la loi cantonale valaisanne sur l'intégration et l'aide sociale, du 29 mars 1996 (LIAS; RS/VS 850.1). Cette loi prévoit l'octroi d'une aide matérielle en vue de couvrir un minimum social, lorsque les mesures propres à assurer l'autonomie financière, par l'intégration professionnelle notamment, ne peuvent être prises ou ne sont pas envisageables (art. 10 al. 2 et 3 LIAS). Pour définir le montant des prestations, un budget d'aide sociale est établi sur la base des recommandations de la Conférence suisse des institutions d'aide sociale (CSIAS; art. 5 al. 2 et 3 du Règlement d'exécution de la loi sur l'intégration et l'aide sociale, du 9 octobre 1996; RS/VS 850.100). En d'autres termes, les prestations d'aide sociale litigieuses sont définies de manière relativement précise par la législation et leur octroi n'est pas laissé à la libre disposition de l'autorité administrative. La procédure cantonale portait donc sur des droits à caractère civil au sens de l'art. 6 par. 1 CEDH.
4. 4.1 Il n'est pas contesté que F._ a demandé la tenue de débats publics. Le 17 décembre 2008, la juridiction cantonale a d'ailleurs adressé aux parties, en courrier recommandé, une convocation à un débat final le 12 janvier 2009, en précisant qu'elle donnait ainsi suite à une demande de F._. Le débat s'est déroulé à la date prévue, en présence de représentants du Conseil d'Etat et de la commune X._. F._ ne s'est en revanche pas présenté. La juridiction cantonale a rendu son jugement le 16 janvier suivant. A réception de ce jugement, F._ a interjeté un recours en matière de droit public en invoquant une violation de l'art. 6 par. 1 CEDH et en précisant qu'il n'avait pas reçu de convocation pour la séance du 12 janvier 2009. Il a également écrit au Tribunal cantonal valaisan, le 22 janvier 2009, pour exposer qu'il n'avait pas reçu de convocation à la «séance de conciliation du 12 janvier 2009»; il a demandé à être convoqué à nouveau. A la suite d'une demande de recherche postale présentée par la juridiction cantonale, il s'est avéré que la convocation du 17 décembre 2008 n'avait effectivement pas été notifiée à F._, ou du moins que cela ne pouvait être établi, sans que la Poste suisse puisse l'expliquer. Il faut en conclure que F._ n'a pas été convoqué régulièrement à la séance du 12 janvier 2009 (cf. <ref-ruling> consid. 3b p. 100; arrêt C 294/99 du 14 décembre 1999 consid. 2a, DTA 2000 no 25 p. 118) et que les débats publics demandés ne se sont pas déroulés valablement en son absence. Par ailleurs, le seul fait que F._ ne mentionne, dans sa lettre du 22 janvier 2009 à la juridiction cantonale, qu'une «séance de conciliation» ne suffit pas pour considérer qu'il aurait désormais renoncé à des débats publics.
4.2 Compte tenu de ce qui précède, la procédure cantonale est entachée d'un vice de procédure qui entraîne d'emblée l'annulation du jugement entrepris, indépendamment des chances de succès du recours sur le fond. Le vice de procédure ne peut pas être réparé en procédure fédérale, compte tenu du pouvoir d'examen limité dont jouit le Tribunal fédéral (art. 95 à 97 LTF; art. 105 LTF; cf. <ref-ruling> consid. 2.2.3 p. 135; <ref-ruling> consid. 3d/aa p. 437). Il n'y a donc pas lieu de donner suite à la demande de débats publics présentée par le recourant en instance fédérale, mais de renvoyer la cause aux premiers juges pour qu'ils le convoquent à une nouvelle audience, puis statuent à nouveau.
5. Le présent arrêt rend sans objet la demande d'octroi de l'effet suspensif au recours et de mesures provisionnelles présentée par le recourant. Compte tenu de l'issue du procès, ce dernier n'encourt pas de frais de justice (art. 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis en ce sens que le jugement du 16 janvier 2009 du Tribunal cantonal valaisan est annulé et la cause renvoyée à cette autorité pour qu'elle statue à nouveau en procédant conformément aux considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal valaisan, et à l'Administration communale X._.
Lucerne, le 3 avril 2009
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral