Sachverhalt:
A. A._ (Beschwerdeführer) und B._ führten im Frühjahr 2003 Gespräche mit dem Vertreter des Sportamtes des Kantons Basel-Stadt (Beschwerdegegner) über die Errichtung eines polysportiven Sportzentrums auf der Anlage S._. Nach dem Scheitern des Projekts versuchte der Beschwerdeführer erfolglos, für seine Bemühungen entschädigt zu werden.
B. Am 7. Oktober 2004 beantragte der Beschwerdeführer dem Zivilgericht Basel-Stadt, den Beschwerdegegner zu verpflichten, ihm Fr. 99'233.-- nebst Zins zu 5 % seit 30. November 2003 zu bezahlen. Mit Urteil vom 20. Juni 2008 wies das Zivilgericht die Klage ab.
Die dagegen vom Beschwerdeführer erhobene Appellation wies das Appellationsgericht des Kantons Basel-Stadt am 21. August 2009 ab und bestätigte das erstinstanzliche Urteil.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, das Urteil des Appellationsgerichts vom 21. August 2009 aufzuheben. Der Beschwerdegegner sei zu verurteilen, ihm Fr. 99'233.-- nebst Zins zu 5 % seit 30. November 2003 zu bezahlen. Eventualiter sei die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Der Beschwerdegegner und die Vorinstanz beantragen, die Beschwerde abzuweisen.
D. Mit Präsidialverfügung vom 10. Dezember 2009 wurde das Gesuch des Beschwerdeführers um Erteilung der aufschiebenden Wirkung abgewiesen.

Erwägungen:
1. Nach Art. 42 Abs. 1 und 2 BGG ist die Beschwerde hinreichend zu begründen, andernfalls wird darauf nicht eingetreten (vgl. <ref-ruling> E. 2.1 S. 245 f.; <ref-ruling> E. 3.3). Die Verletzung von Grundrechten kann das Bundesgericht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 6, 439 E. 3.2). Auf appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 3.1 S. 399). Macht der Beschwerdeführer beispielsweise eine Verletzung von <ref-law> geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich; er hat vielmehr im Einzelnen zu zeigen, inwiefern der angefochtene Entscheid offensichtlich unhaltbar ist (<ref-ruling> E. 5.5 S. 5; <ref-ruling> E. 1.3 S. 262).
2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3).
3. Die Vorinstanz wies die Klage gestützt auf zwei selbständige Begründungen ab: Sie verneinte zum einen, dass der Beschwerdeführer habe beweisen können, dass der Beschwerdegegner ihm einen Auftrag erteilt habe. Zum andern kam sie zum Schluss, der Beschwerdeführer habe seine Forderung nicht genügend dargelegt. Der Beschwerdeführer ficht beide Begründungen an, was nötig ist, damit auf seine Beschwerde eingetreten werden kann (<ref-ruling>).
4. Die Abweisung der Klage mangels genügender Darlegung der Honorarforderung begründete die Vorinstanz damit, dass der Beschwerdeführer ausser der Erstellung des Businessplans keine weiteren Bemühungen konkretisiert habe. Die zeitliche Bezifferung seiner Leistungen mit "68,5 Manntagen" erläutere er ebenso wenig wie den von ihm angewendeten Tagesansatz. Nicht einmal die von ihm erstellte Rechnung sei mit der Klage eingereicht worden.
Der Beschwerdeführer hält dem entgegen, die Vorinstanz habe sein Schreiben vom 30. November 2003 (Klagebeilage 12) nicht berücksichtigt. Dieses Schreiben bestehe erstens aus einer Situationsanalyse, zweitens aus einer sich über drei Seiten erstreckenden Aufstellung der im Rahmen des Projekts erbrachten Dienstleistungen und drittens aus einer Kalkulation des konkreten Rechnungsbetrags.
Dieser Einwand entbehrt der Grundlage, da sich das genannte Aktenstück (Aufstellung der Bemühungen und Kalkulation/Rechnung) nicht bei den Klagebeilagen befindet. Das monierte der Beschwerdegegner bereits in seiner Klageantwort und stellte die Vorinstanz in der Erwägung 3 des angefochtenen Entscheids fest. Da der Beschwerdeführer das Aktenstück nicht rechtzeitig mit der Klage eingereicht hat, kann der Vorinstanz auch nicht vorgeworfen werden, dieses übersehen zu haben. Dass der Beschwerdegegner von der Darstellung und Rechnung Kenntnis genommen haben soll, wie der Beschwerdeführer gestützt auf das Schreiben des Beschwerdegegners vom 12. Januar 2004 vorbringt, ändert nichts daran. Entscheidend ist, ob das Aktenstück prozesskonform ins Recht gelegt wurde. Zudem weist die Vorinstanz in ihrer Vernehmlassung zu Recht auch darauf hin, dass die relevanten Tatsachen in der Rechtsschrift behauptet werden müssen und es nicht genügt, stattdessen bloss auf Beilagen zu verweisen.
Die Vorinstanz ging daher zutreffend davon aus, dass die Klage schon deshalb abzuweisen ist, weil die Forderung nicht genügend dargelegt wurde. Der angefochtene Entscheid vermag sich folglich bereits auf diese Begründung zu stützen. Damit erübrigt es sich, auf die Vorbringen gegen die weitere Begründung der Vorinstanz, der Beschwerdeführer habe die Erteilung eines Auftrags nicht bewiesen, einzugehen. In Kürze seien dazu immerhin die nachstehenden Erwägungen angefügt:
5. Der Beschwerdeführer wirft der Vorinstanz betreffend die Verneinung einer Auftragserteilung mehrere aktenwidrige Feststellungen und die Verletzung der Begründungspflicht vor.
5.1 Er rügt, die Sachverhaltsdarstellung der Vorinstanz trage der "planerischen Ausgangslage" nicht Rechnung. Die Vorinstanz verkenne insbesondere, dass die erste Ansprache auf C._ und damit auf einen Vertreter des Beschwerdegegners zurückgehe. Inwiefern dieser Umstand - sollte er vorliegen - für den Ausgang des Verfahrens entscheidend sein kann, legt der Beschwerdeführer nicht dar. Deshalb ist auf dieses Vorbringen nicht einzutreten (<ref-law>; Erwägung 2).
5.2 Der Beschwerdeführer wirft der Vorinstanz eine Verletzung von <ref-law> vor, weil sie die Aufstellung der einzelnen Bemühungen gemäss Klagebeilage 12 nicht berücksichtigt habe. Wie ausgeführt (Erwägung 4), hat der Beschwerdeführer diese Aufstellung nicht mit der Klage eingereicht. Sie konnte und musste daher auch nicht berücksichtigt werden.
5.3 Weiter macht der Beschwerdeführer eine "unzulässige summarische Würdigung" des Schreibens vom 30. April 2003 (Klagebeilage 2) geltend. Die Vorinstanz erblickte darin mit überzeugender Begründung keine Offerte. Was der Beschwerdeführer dagegen einwendet, begründet keine willkürliche Beweiswürdigung. Er trägt dem Bundesgericht einen Sachverhalt vor, der vom angefochtenen Urteil abweicht. So namentlich wenn er der Vorinstanz vorhält, sie habe die E-Mail vom 5. Mai 2003 (Klagebeilage 3) bei ihrer Würdigung des Schreibens vom 30. April 2003 nicht berücksichtigt, woraus hervorgehe, dass am 5. Mai 2003 eine "bereinigte Offerte" vorgelegt worden sei. Dass er entsprechende Behauptungen zu dieser E-Mail im kantonalen Verfahren prozesskonform eingebracht hätte, wird nicht geltend gemacht, sondern vielmehr von der Vorinstanz in der Vernehmlassung widerlegt.
5.4 Der Beschwerdeführer vermag auch mit seinen Ausführungen zum undatierten Schreiben T._ (Klagebeilage 4) keine aktenwidrige Feststellung des Sachverhalts aufzuzeigen. Er unterbreitet dem Bundesgericht lediglich sein eigenes Verständnis dieses Schreibens, belegt aber nicht einmal, dass er entsprechende Behauptungen im kantonalen Verfahren aufgestellt hätte, welche die Vorinstanz missverstanden haben soll.
Fehl geht auch der Vorwurf, die Vorinstanz differenziere zwischen bisherigen und zukünftigen Teilleistungen, obwohl sich eine solche Unterscheidung aus der Klagebeilage 4 nicht ergebe. Die Vorinstanz führte aus, das Schreiben lasse wesentliche Fragen offen. So seien sich die Parteien zwar offenbar einig gewesen, dass in Zukunft Teilleistungen abzugelten seien, jedoch sei noch nicht festgestanden, welche und in welchem Umfang. Die Vorinstanz unterschied also nicht in bisherige und zukünftige Teilleistungen, sondern meinte, dass in Zukunft Teilleistungen abzugelten wären, wenn die diesbezüglichen Vorgaben vorliegen würden. Von einer angeblich aktenwidrigen Einschränkung auf künftige Teilleistungen kann keine Rede sein. Weiter trägt der Beschwerdeführer unbelegte Behauptungen vor, wenn er etwa darlegt, es sei unbestritten geblieben, dass der Businessplan am 30. Juni 2003 einen ganzen Nachmittag lang im Ressort Sport via Beamer präsentiert und detailliert diskutiert worden sei. Die Vorinstanz und der Beschwerdegegner bestreiten die entsprechende Darlegung.
Der Beschwerdeführer beanstandet weiter die Feststellung der Vorinstanz, auch die als notwendig erachtete Terminierung der Etappen sei weder im Schreiben (Klagebeilage 4) noch zu einem späteren Zeitpunkt erfolgt. Dass diese Feststellung offensichtlich unrichtig ist, zeigt der Beschwerdeführer nicht auf, indem er vorbringt, sowohl aus Klagebeilage 4 als auch aus Klagebeilage 7 lasse sich jeweils einzeln eine Übersicht über die zeitliche Planung gewinnen. Er äussert damit lediglich seine Meinung zu den beiden Klagebeilagen und übersieht einmal mehr, dass die rechtserheblichen Tatsachen in den Rechtsschriften zu behaupten sind. Das Gericht ist nicht gehalten, ohne entsprechende Tatsachenbehauptungen zu forschen, ob sich allenfalls solche aus den Beilagen ergeben. Der Beschwerdeführer macht nicht geltend, er hätte rechtzeitig entsprechende Behauptungen aufgestellt, welche die Vorinstanz übersehen hätte. Mit vor Bundesgericht neu aufgestellten Behauptungen lässt sich aber von vornherein keine aktenwidrige Sachverhaltsfeststellung nachweisen.
5.5 Die weiteren Vorbringen des Beschwerdeführers, mit denen er der Vorinstanz eine einseitige und willkürliche Würdigung der Klagebeilagen 4 und 7 und diverse aktenwidrige Sachverhaltsfeststellungen sowie teilweise eine Verletzung der Begründungspflicht vorwirft, erweisen sich als unzulässige appellatorische Kritik, auf die nicht eingetreten werden kann. Der Beschwerdeführer unterbreitet dem Bundesgericht seine eigene Darstellung und Interpretation des Sachverhalts. Er belegt weder das Vorliegen von Aktenwidrigkeiten noch erfüllt er die strengen Begründungsanforderungen an eine Willkürrüge. Eine Aktenwidrigkeit ergibt sich nicht daraus, dass die Vorinstanz ein Aktenstück anders würdigt, als dies der Beschwerdeführer tut, oder wenn sie aus einer Beilage einen Umstand nicht ableitet, den der Beschwerdeführer gar nicht behauptet hat bzw. dessen rechtzeitiges Vorbringen der Beschwerdeführer nicht belegt. Ebenso wenig liegt eine Verletzung der Begründungspflicht nach <ref-law> vor, wenn der Beschwerdeführer eine Begründung der Vorinstanz für nicht nachvollziehbar hält. Er konkretisiert auch nicht, mit welchen von ihm vorgebrachten wesentlichen Argumenten sich die Vorinstanz nicht auseinandergesetzt haben soll. Eine Verletzung der Begründungspflicht nach <ref-law> wird nicht hinlänglich begründet. Mit seinen appellatorischen Vorbringen scheint der Beschwerdeführer zu verkennen, dass das Bundesgericht keine letzte Appellationsinstanz ist, die von den Parteien mit vollkommenen Rechtsmitteln angerufen werden könnte. Darauf ist nicht einzutreten (vgl. Erwägung 1).
5.6 Die Vorinstanz hielt zusammenfassend fest, dass dem Beschwerdeführer der Nachweis einer Auftragserteilung nicht gelungen sei. Daran ändere nichts, dass berufsmässige Dienstleistungen grundsätzlich entgeltlich seien, wie der Beschwerdeführer meine. Denn dies möge für Ärzte, Anwälte und so weiter zutreffen, sei aber für die Beteiligten bei der Planung grösserer Bauprojekte nicht zwingend. Der Beschwerdeführer hält diese Erwägung für nicht nachvollziehbar und rügt eine Verletzung der Begründungspflicht nach <ref-law> und eine unzulässige Nichtanwendung von <ref-law>.
Die Frage der Entgeltlichkeit des Auftrags stellt sich erst, wenn überhaupt ein Auftrag erteilt wurde. Die Vorinstanz kam vorliegend aber zum Schluss, dass eine Auftragserteilung nicht nachgewiesen ist, auch keine stillschweigende oder konkludente. Bei diesem Beweisergebnis spielt es keine Rolle, dass professionelle Dienstleistungen im Rahmen eines Auftrags üblicherweise entgeltlich sind. Weder eine Verletzung von <ref-law> noch eine solche von <ref-law> ist ersichtlich.
6. Die Beschwerde ist aus diesen Gründen abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (<ref-law>). Eine Parteientschädigung an den in seinem amtlichen Wirkungskreis obsiegenden Kanton Basel-Stadt ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 5'000.-- werden dem Beschwerdeführer auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 5. März 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Klett Sommer