Faits:
A. A._ est propriétaire de la parcelle n° 6030 du registre foncier de la commune de Fully, au lieu-dit "Le Goilly". Cette parcelle de 1'460 m2 est classée dans une zone artisanale différée dans le plan d'affectation communal approuvé le 24 octobre 1984 par le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat). Elle est plantée de framboisiers cultivés sous serres.
A.a Par avis paru au Bulletin officiel du 17 novembre 2000, l'Etat du Valais a mis à l'enquête publique le projet de correction de la route cantonale n° 71 reliant Martigny à Ardon, depuis la jonction d'autoroute Martigny-Fully jusqu'à l'entrée du village de Branson, sur le territoire des communes de Martigny et Fully. Ce projet impliquait l'expropriation d'une surface de 375 m2 de la parcelle n° 6030. Par décision du 13 juin 2002, le Conseil d'Etat a approuvé les plans y relatifs, déclaré les travaux d'utilité publique et rejeté les oppositions dans la mesure de leur recevabilité.
Le 8 mai 2003, A._ et B._, alors copropriétaires pour moitié de la parcelle n° 6030, ont requis l'extension de l'expropriation à l'ensemble du bien-fonds. Ils ont réclamé une indemnité de 66'000 fr. pour le terrain exproprié, une somme de 24'269 fr. en compensation des frais d'installation et de mise en place de la plantation de framboisiers en 2000, une indemnité de 208'480 fr., réduite à 83'392 fr., pour la perte de récolte pendant quatre ans, un montant de 4'000 fr. pour l'expropriation d'un cerisier et 2'000 fr. à titre de dépens.
Par décision du 31 juillet 2003, la Commission d'estimation en matière d'expropriation (ci-après: la Commission d'estimation) a admis l'expropriation totale de la parcelle n° 6030 et fixé le prix d'expropriation du terrain à 40 fr./m2, soit une indemnité de 58'400 fr. pour la perte du droit exproprié. Elle a accordé un montant de 3,49 fr./m2 de surface cultivée sous serres à titre d'indemnité pour la reconstruction des installations et des cultures, uniquement en cas de déménagement et de reconstruction effective sur une autre parcelle par les soins de l'exproprié. Elle a alloué, aux mêmes conditions, un montant de 12,60 fr./m2 par année de surface cultivée sous serre et pour une durée de 4 ans à titre d'indemnité pour les pertes de récolte. Elle a accordé un montant de 1'935 fr. pour le cerisier et refusé les dépens. Le 10 septembre 2003, l'Etat du Valais a déposé une requête en révision à l'encontre de cette décision auprès du Conseil d'Etat. Il soutenait qu'aucune indemnité conditionnelle n'était due pour la perte de récolte et la reconstitution des cultures, ces frais étant compris dans l'indemnité allouée pour la perte de surface calculée sur l'entier de la parcelle. Il relevait que les études de détail relatives à la construction d'un nouveau pont sur le Rhône à Branson se poursuivaient et qu'il n'était pas exclu que la parcelle n° 6030 ne soit finalement plus expropriée.
A.b Le 10 mars 2004, le Service cantonal des routes et des cours d'eau a informé A._ que le projet d'exécution avait été modifié, que les travaux prévus en 2004 ne concerneraient que la construction du pont et ne nécessiteraient aucune emprise sur la parcelle n° 6030 de sorte qu'il pouvait exploiter en totalité la parcelle pour l'année 2004. Par avis paru au Bulletin officiel du 13 janvier 2006, l'Etat du Valais a mis à l'enquête publique complémentaire les modifications apportées au projet d'exécution initial, qui réduisaient la surface expropriée de la parcelle n° 6030 à 44 m2. Le Conseil d'Etat a approuvé ces nouveaux plans et a déclaré les travaux projetés d'utilité publique.
Le 23 mai 2006, A._ et B._ ont émis des prétentions relatives à cette nouvelle situation. Ils réclamaient une indemnité de 1'760 fr. pour le terrain exproprié, à raison de 40 fr./m2, une somme de 14'160 fr. pour la moins-value affectant le solde de la parcelle, à raison de 10 fr./m2, une indemnité de 24'269 fr. pour les frais de réinstallation et de remise en place de la plantation de framboisiers en 2004, un montant de 36'792 fr., ramené par la suite à 28'526 fr., pour la perte de récolte pendant deux ans et une indemnité de 1'935 fr. pour le cerisier. Ils sollicitaient en outre une indemnité de dépens ainsi que le rétablissement des conduites et des accès.
Par décision du 16 octobre 2006, qui remplace celle du 31 juillet 2003, la Commission d'estimation a alloué un prix de 40 fr./m2, soit 1'760 fr., pour la valeur du terrain exproprié de la parcelle n° 6030, avec intérêts dus dès la prise de possession effective. Elle a admis l'indemnité pour le cerisier et le rétablissement des conduites et des accès aux frais du maître de l'ouvrage. Elle a rejeté toutes les autres prétentions émises et refusé d'allouer des dépens.
A.c Le 17 novembre 2006, A._ et B._ ont déposé une réclamation contre cette décision auprès du Conseil d'Etat, en concluant à l'octroi d'une indemnité de 94'616 fr. avec intérêts au taux légal dès le 18 octobre 2006, date de la prise de possession. Le 9 mai 2007, A._, resté seul propriétaire de la parcelle n° 6030, a sollicité une indemnité pour la surface expropriée de 3'300 fr., soit un montant de 55 fr./m2, une indemnité de moins-value de 38'500 fr. pour le solde de la parcelle, correspondant au 50% de la valeur du terrain, un défraiement de 24'269 fr. pour la réinstallation et la remise en place de la plantation de framboisiers en 2004, une indemnité de 36'792 fr. pour la perte de récolte pendant deux ans et le maintien de l'indemnité de 1'935 fr. pour le cerisier, soit un montant total de 104'796 fr. avec intérêts dès le 18 octobre 2006. Il réclamait en outre une indemnité pour ses dépens ainsi que le rétablissement des conduites et des accès.
Par décision du 13 juin 2007, la Commission de révision désignée par le Conseil d'Etat en vertu de l'art. 11 de l'ancienne loi cantonale concernant les expropriations pour cause d'utilité publique, du 1er décembre 1887 (aLEx/VS) a proposé l'expropriation totale de la parcelle n° 6030 pour le prix de 50 fr./m2 avec une indexation de 25% sur 4 ans. Elle a confirmé l'indemnité de déménagement et de reconstruction fixée le 31 juillet 2003 par la Commission d'estimation, soit 3,49 fr./m2. D'entente avec le Service cantonal des routes et des cours d'eau, elle a mis à la disposition de A._, sans frais de location, l'exploitation du terrain jusqu'au 31 décembre 2008.
A.d A._ a recouru contre cette décision auprès de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) en concluant à l'octroi d'une somme de 103'101 fr. en cas d'expropriation partielle de sa parcelle et de 138'922 fr. en cas d'expropriation totale. Par arrêt du 13 décembre 2007, cette autorité lui a donné acte de l'expropriation totale de la parcelle n° 6030 pour le prix de 50 fr./m2, de l'indemnité de 1'935 fr. pour le cerisier, de l'indemnité de 3,49 fr./m2 en cas de déménagement et de reconstruction des installations de culture sous serres sur une autre parcelle et de la possibilité d'exploiter la parcelle n° 6030 sans location jusqu'au 31 décembre 2008. Elle a rejeté le recours dans toutes ses autres conclusions qui n'étaient pas sans objet.
B. Le prénommé a contesté cet arrêt auprès du Tribunal fédéral. Par arrêt du 24 juin 2008 (1C_55/2008), la Cour de céans a admis ce recours, annulé l'arrêt attaqué et renvoyé la cause à la cour cantonale pour nouvelle décision. En substance, le Tribunal cantonal avait considéré arbitrairement que le débat était limité devant lui à la question d'une expropriation totale, de sorte qu'il devait également se prononcer sur les conclusions principales en expropriation partielle, le cas échéant après avoir renvoyé la cause à la Commission de révision pour que celle-ci statue sur ces questions en première instance. Par ailleurs, c'était à tort que le Tribunal cantonal avait refusé toute indemnité pour perte de récolte pour les années 2004 et 2005. Compte tenu des circonstances, on ne pouvait pas reprocher à l'intéressé de ne pas avoir effectué des travaux de taille et d'entretien durant l'automne 2003, en vue d'une récolte qu'il n'était pas certain de pouvoir réaliser l'année suivante. Il convenait dès lors de déterminer si au printemps 2004 il était trop tard pour sauver les plantations et si une perte de récolte pour les années 2004 et 2005 était suffisamment établie. Le Tribunal cantonal était invité à se prononcer à nouveau sur cette question, le cas échéant après avoir consulté un expert ou renvoyé la cause à la Commission de révision. Enfin, le refus par principe de verser des dépens pour les procédures d'estimation et de révision était lui aussi arbitraire et le Tribunal cantonal était enjoint de statuer sur ce point, en précisant les conditions auxquelles il entendait subordonner l'octroi de dépens.
Par arrêt du 22 août 2008, le Tribunal cantonal a admis partiellement le recours déposé le 20 août 2007 par A._, annulé la décision de la Commission de révision du 13 juin 2007 et renvoyé la cause à cette autorité pour nouvelle décision. Il s'agissait notamment de déterminer précisément la surface expropriée, de trancher la question d'une éventuelle indemnité pour perte de récolte pour les années 2004 et 2005 et de statuer sur les dépens. La Commission de révision a rendu une nouvelle décision le 28 novembre 2008. Elle a alloué une indemnité de 50 fr./m2 pour les 44 m2 expropriés, soit 2'200 fr., une indemnité de moins value de 50 % de la valeur du terrain (25 fr./m2) sur 300 m2, soit 7'500 fr., une indemnité de 1'935 fr. pour le cerisier, le rétablissement des conduites et des accès aux frais du maître de l'ouvrage et, enfin, une indemnité de 1'000 fr. à titre de dépens.
A._ a contesté cette décision auprès du Tribunal cantonal, en demandant que l'indemnité de moins value de 25 fr./m2 soit octroyée pour tout le solde de la parcelle, soit 1'416 m2, qu'une indemnité pour pertes de récoltes soit allouée sur deux ans (28'526 fr.) et que les dépens soient fixés à 16'000 francs. Le Tribunal cantonal a admis partiellement ce recours par arrêt du 21 août 2009. Il a réformé la décision attaquée en ce sens que l'indemnité pour moins-value de 25 fr./m2 était allouée sur 392 m2 (soit 9'300 fr. au total) et que l'indemnité pour dépens était portée à 1'400 francs.
C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler cet arrêt et de renvoyer la cause au Tribunal cantonal pour nouvelle décision après instruction complémentaire et respect de son droit d'être entendu. Il conclut subsidiairement à la réforme de l'arrêt attaqué et à l'allocation, en sus des montants accordés par l'arrêt en question, d'une indemnité de 28'526 fr. pour perte de récolte et d'une indemnité totale de 35'400 fr. ("dont à déduire les 9'300 fr. déjà alloués par l'arrêt attaqué") pour la moins-value du solde de sa parcelle. Il se plaint en substance d'une violation de son droit d'être entendu (art. 29 al. 2 Cst.) et d'arbitraire (art. 9 Cst.). Renonçant à se déterminer, le Tribunal cantonal conclut néanmoins au rejet du recours. L'Etat du Valais a présenté des observations, au terme desquelles il conclut au rejet du recours.

Considérant en droit:
1. Dirigé contre une décision rendue dans une cause d'expropriation, le recours est recevable comme recours en matière de droit public (art. 82 let. a LTF), aucune des exceptions prévues à l'art. 83 LTF n'étant réalisée. Le recourant a pris part à la procédure de recours devant le Tribunal cantonal et il est particulièrement touché par l'arrêt attaqué, qui lui alloue une indemnité pour expropriation largement inférieure à celle qu'il avait requise. Il a donc la qualité pour agir au sens de l'art. 89 al. 1 LTF. Pour le surplus, interjeté en temps utile contre une décision finale prise en dernière instance cantonale non susceptible de recours devant le Tribunal administratif fédéral, le recours est recevable au regard des art. 86 al. 1 let. d, 90 et 100 al. 1 LTF.
2. Dans un premier grief, le recourant se plaint d'une violation de son droit d'être entendu au sens de l'art. 29 al. 2 Cst. Il soutient n'avoir pas eu connaissance à temps d'un document déterminant et il reproche au Tribunal cantonal d'avoir considéré à tort que ce vice avait été guéri.
2.1 Tel qu'il est garanti à l'art. 29 al. 2 Cst., le droit d'être entendu comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, le droit de consulter le dossier et de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.2 p. 494, V 368 consid. 3.1 p. 371; <ref-ruling> consid. 2.2 p. 504 s.; <ref-ruling> consid. 2b p. 56; <ref-ruling> consid. 3a p. 51 et les arrêts cités). Le droit de consulter le dossier s'étend à toutes les pièces décisives (<ref-ruling> consid. 2a p. 227 et les références citées). Il en découle notamment que l'autorité qui verse au dossier de nouvelles pièces dont elle entend se prévaloir dans son jugement est tenue en principe d'en aviser les parties, même si elle estime que les documents en question ne contiennent aucun nouvel élément de fait ou de droit (<ref-ruling> consid. 2c p. 100, confirmé par l'<ref-ruling> consid. 3 p. 388 s.).
Par exception au principe de la nature formelle du droit d'être entendu, une violation de ce dernier est considérée comme réparée lorsque l'intéressé jouit de la possibilité de s'exprimer librement devant une autorité de recours disposant du même pouvoir d'examen que l'autorité inférieure, et qui peut ainsi contrôler librement l'état de fait et les considérations juridiques de la décision attaquée (<ref-ruling> consid. 2.2 p. 204; <ref-ruling> consid. 2.2.3 p. 135; <ref-ruling> consid. 3d/aa p. 437; <ref-ruling> consid. 2b p. 132). Toutefois, la réparation de la violation du droit d'être entendu doit rester l'exception (ATF 126 V précité) et n'est admissible que dans l'hypothèse d'une atteinte qui n'est pas particulièrement grave aux droits procéduraux de la partie lésée. Si par contre l'atteinte est importante, il n'est pas possible de remédier à la violation (<ref-ruling> consid. 4b).
2.2 En l'occurrence, le Tribunal cantonal a constaté que le recourant n'avait pas eu connaissance d'une lettre adressée le 18 septembre 2006 par le chef de l'Office cantonal d'arboriculture, d'horticulture et de cultures maraîchères à la présidente de la Commission d'estimation. Il relève que ce document a servi de base à la décision de la Commission d'estimation du 16 octobre 2006 et qu'il était expressément cité dans la décision rendue le 13 juin 2007 par la Commission de révision, cette autorité qualifiant d'expert l'auteur de ce courrier. Or, le document en question ne figurait pas au dossier tel qu'il a été transmis au Tribunal cantonal et au Tribunal fédéral dans le cadre des précédents recours. Ce n'est qu'en 2009, dans le cadre du deuxième recours formé devant le Tribunal cantonal, que le recourant a pu prendre connaissance de ce courrier. Le Tribunal cantonal a dès lors constaté que le droit d'être entendu du recourant avait été violé. Il a cependant estimé que cette violation avait été guérie, dans la mesure où l'intéressé avait eu connaissance de la teneur du document en question par la décision de la Commission d'estimation du 16 octobre 2006 et qu'il avait pu se déterminer matériellement à cet égard dans sa réclamation du 17 novembre 2006.
2.2.1 Dans le courrier litigieux du 18 septembre 2006, l'office consulté répond à des questions de la présidente de la Commission d'estimation relatives à d'éventuelles pertes de récolte. Dans sa décision du 16 octobre 2006, cette autorité cite le courrier en cause de manière tronquée, en relevant seulement que "l'expert" avait considéré qu'il était possible de procéder à la taille des vielles cannes au printemps pour continuer l'exploitation de la culture en place. La Commission d'estimation omet de mentionner que "l'expert" a également relevé que la réalisation de cette opération au printemps nécessitait nettement plus de temps et qu'elle pourrait entraîner une perte de récolte. Dans ces conditions, on ne peut guère suivre le Tribunal cantonal lorsqu'il affirme que le recourant a eu connaissance de la teneur du document litigieux par le biais de la décision du 16 octobre 2006, l'intéressé n'ayant eu qu'une vision très partielle de cet avis, dont il aurait également pu tirer argument en sa faveur plus tôt s'il en avait eu pleinement connaissance.
2.2.2 Il n'en demeure pas moins que le recourant a pu contester utilement la position de la Commission d'estimation, en se fondant sur une autre "expertise". Il s'est en outre largement exprimé sur la question de la perte de récolte, notamment dans son recours du 17 novembre 2006 au Conseil d'Etat et dans ses recours des 20 août 2007 et 19 janvier 2009 au Tribunal cantonal. De plus, il a pu consulter le document litigieux lors de la deuxième procédure de recours devant le Tribunal cantonal - qui dit avoir en l'occurrence un pouvoir d'examen libre, sans être contredit sur ce point - et il a saisi l'occasion de se déterminer à son sujet dans ses observations du 20 avril 2009. Dans ces conditions, contrairement à ce que prétend le recourant, la violation de son droit d'être entendu ne revêt pas une gravité telle qu'une guérison au sens de la jurisprudence susmentionnée serait impossible. Aussi regrettable qu'il soit, le refus de la Commission d'estimation de verser ce document au dossier n'a en définitive pas porté préjudice au recourant. Celui-ci a pu faire valoir ses droits à cet égard et le Tribunal cantonal a pu trancher la question litigieuse en connaissance de cause. C'est donc à bon droit que cette autorité a constaté que la violation du droit d'être entendu avait été guérie.
2.2.3 Pour le surplus, le recourant reproche au Tribunal cantonal d'avoir refusé d'auditionner l'auteur du document litigieux et d'administrer divers moyens de preuve supplémentaires. Il ne conteste cependant pas les motifs avancés pour rejeter ces moyens et il ne démontre pas en quoi cette appréciation anticipée des preuves serait entachée d'arbitraire, de sorte qu'il n'y a pas lieu de s'en écarter.
3. Dans un deuxième grief, le recourant se plaint du "non-respect des considérants du Tribunal fédéral", en se référant à l'arrêt 1C_55/2008 précité ainsi qu'à son recours déposé le 19 janvier 2009 devant le Tribunal cantonal. Cependant, contrairement à ce que semble soutenir le recourant, le Tribunal cantonal n'a pas refusé l'indemnité pour perte de récoltes parce que l'intéressé aurait eu tort de renoncer à effectuer des travaux d'entretien en automne 2003, mais bien parce que le dommage allégué n'avait aucunement été démontré (cf. arrêt attaqué consid. 4c). Il n'y a donc pas de contradiction manifeste avec l'arrêt 1C_55/2008, de sorte que ce grief doit être rejeté.
4. Les autres moyens du recours ont trait à l'interdiction de l'arbitraire.
4.1 Selon la jurisprudence, l'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral ne s'écarte de la solution retenue en dernière instance cantonale que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté ou si elle heurte de manière choquante le sentiment de la justice ou de l'équité. Il ne suffit pas que la motivation de la décision soit insoutenable; encore faut-il qu'elle soit arbitraire dans son résultat (<ref-ruling> consid. 3.1 p. 265 s.; <ref-ruling> consid. 3.1 p. 153 et les arrêts cités). En matière d'appréciation des preuves et d'établissement des faits, il y a arbitraire lorsque l'autorité n'a manifestement pas compris le sens et la portée d'un moyen de preuve, si elle ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision ou lorsqu'elle tire des constatations insoutenables des éléments recueillis (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2a p. 41).
4.2 Le recourant critique d'abord les constatations de fait du Tribunal cantonal relatives à la perte de récolte alléguée. Il prétend en substance que le courrier du 18 septembre 2006 sur lequel se fonde l'autorité intimée signifie seulement que la taille est possible au printemps si elle n'a pas été effectuée en automne, ce document n'abordant pas la question des autres travaux qui seraient nécessaires en automne. Or, on ne voit pas en quoi l'arrêt attaqué s'écarterait de manière inadmissible de ce courrier, puisqu'il ne dit pas autre chose. S'il évoque d'"autres travaux" qui ne sont "pas impérativement à réaliser" à l'automne, c'est pour répondre aux arguments du recourant, qui se prévalait d'une "expertise privée" mentionnant de tels travaux. On comprend donc que le Tribunal cantonal explique que, contrairement à "l'expertise privée" en question, l'avis du 18 septembre 2006 ne mentionne pas de travaux qui doivent être impérativement effectués en automne. L'appréciation des preuves ne prête donc pas le flanc à la critique à cet égard. Pour le surplus, le Tribunal cantonal a exposé les raisons pour lesquelles il ne partageait pas le point de vue de "l'expert privé" du recourant, en mentionnant les sources sur lesquelles il fondait son appréciation. Dès lors que celle-ci n'est pas valablement contestée, il n'y a pas lieu de s'en écarter. Il convient de préciser à cet égard qu'il ne suffit pas de rappeler la teneur d'un moyen de preuve écarté de façon motivée pour démontrer une appréciation arbitraire de celui-ci. Pour le surplus, le recourant ne remet pas en cause l'appréciation du Tribunal cantonal selon laquelle le dommage allégué est théorique et n'est aucunement établi. En définitive, le recourant ne parvient pas à démontrer que l'autorité intimée a fait preuve d'arbitraire dans l'appréciation des preuves ou l'établissement des faits, de sorte que ce moyen doit être rejeté.
4.3 Enfin, c'est également sous l'angle de l'arbitraire que le recourant s'en prend au calcul de la moins-value de sa parcelle, en reprenant pour l'essentiel les arguments qu'il avait présentés au Tribunal cantonal. Il reproche à celui-ci de n'avoir pas pris en compte les autres moins-values dont il se prévalait et de n'avoir pas suivi l'avis des taxateurs officiels de la Commune de Fully, qui évaluaient la perte de valeur du bien-fonds concerné à 50 % au minimum. Le recourant présente en outre ses propres calculs, qui reposent sur des éléments de fait qui ne ressortent pas de l'arrêt attaqué, tels que les surfaces nécessaires aux manoeuvres d'accès à sa parcelle. Ce faisant, il perd de vue que le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Le recourant ne peut critiquer la constatation de faits, susceptibles d'avoir une influence déterminante sur l'issue de la procédure, que si ceux-ci ont été établis de manière manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF, en particulier en violation de l'interdiction constitutionnelle de l'arbitraire (art. 97 al. 1 LTF; <ref-ruling> consid. 4.3 p. 62), ce qu'il lui appartient de démontrer par une argumentation répondant aux exigences de l'art. 42 al. 2 LTF, respectivement de l'art. 106 al. 2 LTF (<ref-ruling> consid. 1.4.3 p. 254 s.). Une telle démonstration faisant défaut en l'espèce, il n'y a pas lieu de s'écarter des faits retenus dans la décision attaquée.
Au demeurant, le Tribunal cantonal s'est prononcé de manière circonstanciée sur ces questions et il a exposé les raisons pour lesquelles il n'avait pas pris en considération les moins-values alléguées par l'intéressé ni l'évaluation des taxateurs précités. Le recourant ne démontre pas à satisfaction de droit en quoi cette appréciation serait arbitraire au sens de la jurisprudence susmentionnée. Il se limite en effet à réitérer son point de vue et à affirmer que son appréciation était préférable à celle de l'autorité intimée, qu'il qualifie d'insoutenable sans davantage de motivation. Il n'appartient pas au Tribunal fédéral de réexaminer toutes ces questions en détail, comme le ferait une autorité de première instance. Le caractère insoutenable de l'appréciation contestée n'étant pas démontré, ce moyen doit lui aussi être rejeté.
5. Il s'ensuit que le recours doit être rejeté, dans la mesure de sa recevabilité. Le recourant, qui succombe, doit supporter les frais de la présente procédure (art. 66 al. 1 LTF). Il n'est pas alloué de dépens (art. 68 al. 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté, dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué au mandataire du recourant, à l'Etat du Valais et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 25 novembre 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener