Sachverhalt:
A. Das Bundesamt für Kommunikation (BAKOM) teilte mit Zuteilungsverfügung vom 8. November 1996 dem Touring Club Schweiz, Patrouille TCS (im Folgenden: TCS), die Kurznummer 140 unbefristet für die ganze Schweiz zur Nutzung zu. Das Dienstangebot wurde als "Strassenhilfe" und die Dienstleistung als "Hilfe bei Fahrzeugpannen" umschrieben. Die Verfügung enthielt die Auflage, das BAKOM könne die gemeinsame Nutzung der Kurznummer verlangen, wenn weitere Anbieter dieselbe Dienstleistung anbieten wollten.
B. Mit Verfügung vom 6. September 2010 stellte das BAKOM fest, dass die Mondial Assistance (Schweiz) die Bedingungen für die Zuteilung der Kurznummer 140 erfülle und keine Ausnahmesituation vorliege, welche deren Reservierung allein für den TCS rechtfertigen würde, weshalb der TCS und Mondial Assistance (Schweiz) die Kurznummer 140 gemeinsam zu nutzen hätten (Ziff. 1 und 2 der Verfügung). In Ziff. 3 der Verfügung hielt das BAKOM fest, das Verfahren werde im Hinblick auf die Modalitäten der gemeinsamen Nutzung weitergeführt, sofern die Mondial Assistance (Schweiz) ihm nicht innert drei Monaten nach Eintritt der Rechtskraft der Verfügung mitteile, dass sie sich mit dem TCS über die gemeinsame Nutzung der Kurznummer 140 geeinigt habe. Die gegen diese Verfügung erhobene Beschwerde wies das Bundesverwaltungsgericht mit Urteil vom 7. Juni 2011 ab.
C. Mit Eingabe vom 14. Juli 2011 führt der TCS Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und stellt die folgenden Rechtsbegehren:
"1. Es sei festzustellen, dass die vorliegende Beschwerde den Eintritt der formellen Rechtskraft des angefochtenen Entscheids hemmt und dass die dreimonatige Frist gemäss Dispositiv Ziff. 3 der Verfügung des BAKOM vom 6. September 2010 mit dem das vorliegende Verfahren abschliessenden Entscheid zu laufen beginnt. Eventualiter sei der Beschwerde die aufschiebende Wirkung zu erteilen.
2. Der angefochtene Entscheid sei aufzuheben und es sei festzustellen, dass der Beschwerdeführer die Kurznummer 140 nicht gemeinsam mit der Beschwerdegegnerin zu nutzen hat.
3. Eventualiter sei der angefochtene Entscheid aufzuheben und die Angelegenheit zu neuer Entscheidung im Sinn der nachfolgenden Beschwerdebegründung an die Vorinstanz bzw. an das BAKOM zurückzuweisen.
4. [...]"
Gerügt wird die Verletzung des Legalitätsprinzips und des Rechtsgleichheitsgebots, eine formelle Rechtsverweigerung sowie die falsche Anwendung von Bundesrecht.
D. Das Bundesverwaltungsgericht verzichtet auf eine Vernehmlassung. Das BAKOM beantragt die Abweisung der Beschwerde und die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei.
Mit Verfügung vom 1. September 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung festgestellt, dass die Beschwerde vom 14. Juli 2011 den Eintritt der formellen Rechtskraft des angefochtenen Urteils hemmt und die dreimonatige Frist gemäss Ziff. 3 des Dispositivs der Verfügung des BAKOM vom 6. September 2010 erst mit dem Endurteil des Bundesgerichts zu laufen beginnt. Soweit weitergehend, hat er das Gesuch um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. 1.1 Der in Anwendung des Fernmeldegesetzes vom 30. April 1997 (FMG; SR 784.10) und der gestützt darauf erlassenen Verordnung vom 6. Oktober 1997 über die Adressierungselemente im Fernmeldebereich (AEFV; SR 784.104) ergangene Entscheid der Vorinstanz kann mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht angefochten werden (Art. 82 lit. a und 86 Abs. 1 lit. a BGG); eine Ausnahme nach Art. 83 lit. p BGG liegt nicht vor. Der Beschwerdeführer hat vor der Vorinstanz am Verfahren teilgenommen, ist als direkter Adressat des angefochtenen Urteils von diesem besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung, weshalb er zur Beschwerde berechtigt ist (vgl. <ref-law>).
1.2 Die Beschwerde an das Bundesgericht ist gegen End- und Teilentscheide zulässig (Art. 90 und 91 BGG), gegen Zwischenentscheide hingegen nur unter bestimmten Voraussetzungen (Art. 92 und 93 BGG). Der Endentscheid schliesst ein Verfahren endgültig und vollständig ab. Der Teilentscheid ist eine Variante des Endentscheids. Mit ihm wird über eines oder einige von mehreren Rechtsbegehren abschliessend befunden; es handelt sich dabei nicht um verschiedene materielle Teilfragen eines Rechtsbegehrens, sondern um selbstständige in sich geschlossene, vom sonstigen Streitgegenstand abgrenzbare Rechtsbegehren (vgl. <ref-ruling> E. 4.1.2 S. 480 f. mit erläuternden Hinweisen).
Die Vorinstanz hat die Frage offen gelassen, ob es sich bei der Verfügung des BAKOM vom 6. September 2010 um einen feststellenden Teilentscheid in der Hauptsache, der wie ein Endentscheid angefochten werden kann, oder um eine selbständig eröffnete Zwischenverfügung handelt (vgl. angefochtener Entscheid E. 1.1.1). Auch im Verfahren vor Bundesgericht kann die Frage offen gelassen werden, da die Beschwerde gemäss <ref-law> gegen eine Zwischenverfügung zulässig ist, wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutsamen Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde. Dies trifft hier zu, da bei einer Gutheissung der Beschwerde die Weiterführung des Verfahrens in Hinblick auf die gemeinsame Nutzung der Kurznummer hinfällig würde.
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie ihn die Vorinstanz festgestellt hat (<ref-law>). Es kann diesen bloss berichtigen oder ergänzen, wenn er offensichtlich unrichtig, unvollständig oder in Verletzung wesentlicher Verfahrensrechte ermittelt wurde (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
1.4 Die Beschwerdeschrift hat gemäss <ref-law> die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling> E. 2.1 S. 245 f.). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insoweit, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>).
2. 2.1 Gemäss <ref-law> verwaltet das Bundesamt die Adressierungselemente unter Beachtung der internationalen Normen. Es ergreift die geeigneten Massnahmen zur Gewährleistung einer genügenden Anzahl von Nummerierungselementen und Kommunikationsparametern. Zu den Adressierungselementen gehören auch die Kurznummern (<ref-law>; vgl. auch FISCHER/SIDLER in: Rolf H. Weber [Hrsg.], SBVR Bd. V/1, Informations- und Kommunikationsrecht, 2. Aufl. 2003, B Rz. 266 und 282 f.). Gemäss <ref-law> vollzieht der Bundesrat das Gesetz.
2.2 <ref-law> hält unter der Marginalie "Zuteilungsbedingungen" dazu fest, dass das BAKOM u.a. für Rettungs- und Pannendienste eine Kurznummer zuteilen kann, wenn der entsprechende Dienst jederzeit in der gesamten Schweiz und in den drei Amtssprachen zur Verfügung steht. Wollen mehrere Dienstanbieterinnen einen ähnlichen Dienst anbieten, müssen sie die gleiche Kurznummer gemeinsam nutzen (Abs. 2). Das BAKOM kann Ausnahmen gewähren, wenn die Bedingung der jederzeitigen, landesweiten Verfügbarkeit oder die Verwendung der gleichen Kurznummer eine unverhältnismässige Härte darstellen würde (Abs. 3). Kurznummern bestehen grundsätzlich aus drei Ziffern, von denen die erste eine 1 ist (Format = 1xx). Das BAKOM kann sie um eine oder zwei Zusatzziffern erweitern (<ref-law>). Weiter bestimmt <ref-law>, dass das BAKOM der Gesuchstellerin eine Kurznummer zuteilen kann, wenn diese Dienstleistungen von allgemeinem Nutzen in den Bereichen Rettungsdienste oder Pannendienste anbieten will, die das unverzügliche Eingreifen von Fachleuten vor Ort erfordern.
3. 3.1 Der Beschwerdeführer macht zunächst geltend, <ref-law> sei gesetzeswidrig. Es handle sich um eine reine Vollziehungsverordnung, welche keine über das Gesetz hinausgehenden Pflichten begründen könne. Mit dem Erlass von <ref-law> habe der Bundesrat, ohne dazu kompetent zu sein, eine Bestimmung erlassen, welche den Normadressaten Pflichten auferlege, die das Gesetz nicht vorsehe. Damit werde das Ermessen, das der Gesetzgeber dem Bundesamt in <ref-law> eingeräumt habe, beschnitten und es liege ein Verstoss gegen das Legalitätsprinzip vor.
3.2 Nach der Rechtsprechung kann das Bundesgericht Verordnungen des Bundesrates grundsätzlich, von hier nicht in Betracht fallenden Ausnahmen abgesehen, auf ihre Rechtmässigkeit hin überprüfen. Bei unselbstständigen Verordnungen, die sich auf eine gesetzliche Delegation stützen, geht es in erster Linie darum, zu beurteilen, ob sie sich im Rahmen der Delegationsnorm halten. Besteht ein sehr weiter Spielraum des Ermessens für die Regelung auf Verordnungsebene, muss sich das Gericht auf die Prüfung beschränken, ob die umstrittenen Vorschriften offensichtlich aus dem Rahmen der im Gesetz delegierten Kompetenzen herausfallen oder aus andern Gründen verfassungs- oder gesetzwidrig sind (vgl. <ref-law>). Es kann sein eigenes Ermessen nicht an die Stelle desjenigen des Bundesrates setzen, und es hat auch nicht die Zweckmässigkeit zu untersuchen (<ref-ruling> E. 3.4.1 S. 14; <ref-ruling> E. 3.2 S. 566, 735 E. 4.1 S. 740). Die vom Bundesrat verordnete Regelung verstösst allerdings dann gegen das Willkürverbot oder das Gebot der rechtsgleichen Behandlung (Art. 9 und <ref-law>), wenn sie sich nicht auf ernsthafte Gründe stützen lässt, wenn sie sinn- oder zwecklos ist oder wenn sie rechtliche Unterscheidungen trifft, für die sich ein vernünftiger Grund nicht finden lässt. Gleiches gilt, wenn die Verordnung es unterlässt, Unterscheidungen zu treffen, die richtigerweise hätten berücksichtigt werden sollen (<ref-ruling> E. 2.3 S. 166, 271 E. 4 S. 275; <ref-ruling> E. 5.1 S. 266; <ref-ruling> E. 6.1 S. 473; <ref-ruling> E. 2.2.1 S. 32; <ref-ruling> E. 2.3 S. 164; <ref-ruling> E. 4.1.1 S. 271, 327 E. 4.1 S. 329, je mit Hinweisen; vgl. auch <ref-ruling> E. 4.3 S. 45).
3.3 Der angefochtene Entscheid geht in E. 5.4 von der dargestellten Rechtsprechung aus und hat diese korrekt angewendet: Zunächst hat die Vorinstanz richtig erkannt, dass die gesetzlichen Grundlagen in den Art. 28 ff. in Verbindung mit <ref-law> dem Bundesrat einen sehr weiten Spielraum für den Erlass der erforderlichen Ausführungsbestimmungen zugestanden haben. Entgegen der Auffassung des Beschwerdeführers kann die AEFV nicht als reine Vollzugsverordnung betrachtet werden: Denn wenn <ref-law> das Bundesamt beauftragt, die Adressierungselemente zu verwalten, so wird damit zwangsläufig die nähere Regelung dieser Elementenverwaltung im Sinne von <ref-law> delegiert, wobei diese Rechtssetzungsdelegation grundsätzlich an den Bundesrat geht, der sie für die notwendigen administrativen und technischen Vorschriften an das Bundesamt übertragen kann (<ref-law>; vgl. Art. 48 Abs. 2 RVOG). Damit beschränkt sich das Bundesgericht auf die Prüfung, ob die umstrittenen Vorschriften offensichtlich aus dem Rahmen der im Gesetz delegierten Kompetenzen herausfallen oder aus andern Gründen verfassungs- oder gesetzwidrig sind. Diese Frage ist in Übereinstimmung mit der Vorinstanz zu verneinen: Die Regelung von <ref-law> kann mit Blick auf die mathematisch begrenzte Verfügbarkeit von Kurznummern bzw. eine diskriminierungsfreie Nummernzuteilung ohne Weiteres als sinnvoll und sachgerecht betrachtet werden (vgl. auch Botschaft zum revidierten Fernmeldegesetz vom 10. Juni 1996, BBl 1996 III 1435 Ziff. 24.04; FISCHER/SIDLER, a.a.O., B. Rz. 266 und 283; NOBEL/WEBER, Medienrecht, 3. Aufl. 2007, S. 371). Insbesondere folgt aus dem in <ref-law> enthaltenen Auftrag an das Bundesamt, eine genügende Anzahl von Nummerierungselementen zu gewährleisten, kein Anspruch auf die exklusive Nutzung eines bestimmten Adressierungselementes durch einzelne Benutzer (vgl. <ref-law>).
Der Bundesrat hat somit den Rahmen der Ermächtigung gemäss <ref-law> nicht überschritten, wenn er in <ref-law> bestimmte, dass Dienstleistungsanbieterinnen die gleiche Kurznummer gemeinsam nutzen müssen, wenn sie einen ähnlichen Dienst anbieten. Der blosse Umstand, dass eine andere Lösung, wie sie auch die Beschwerdegegnerin ursprünglich angestrebt hat, allenfalls denkbar gewesen wäre, macht die Verordnungsregelung noch nicht rechtswidrig.
4. 4.1 Der Beschwerdeführer führt sodann aus, die gemeinsame Nutzung der Kurznummer 140 verstosse gegen den Anspruch auf Rechtsgleichheit, weil die Anbieterinnen von Telefonauskunfts- bzw. Helikopterrettungsdiensten - im Gegensatz zu ihm - je eine eigene vierstellige Kurznummer nutzen könnten. Es gäbe keinen sachlichen Grund für eine solche Ungleichbehandlung.
4.2 Das Gebot der rechtsgleichen Behandlung (<ref-law>) ist verletzt, wenn Gleiches nicht nach Massgabe seiner Gleichheit gleich oder Ungleiches nicht nach Massgabe seiner Ungleichheit ungleich behandelt wird. Der Anspruch auf rechtsgleiche Behandlung wird insbesondere verletzt, wenn hinsichtlich einer entscheidwesentlichen Tatsache rechtliche Unterscheidungen getroffen werden, für die ein vernünftiger Grund in den zu regelnden Verhältnissen nicht ersichtlich ist, oder wenn Unterscheidungen unterlassen werden, die aufgrund der Verhältnisse hätten getroffen werden müssen (vgl. <ref-ruling> E. 6.1 S. 237 mit Hinweisen).
4.3 Im vorinstanzlichen Verfahren hatte der Beschwerdeführer eine Verletzung des Gebots der Rechtsgleichheit noch mit dem Argument gerügt, die Dienstleistungen des Beschwerdeführers würden sich in wesentlichen Punkten von jenen der Beschwerdegegnerin unterscheiden, weshalb sich eine Ungleichbehandlung rechtfertige. Die Vorinstanz hat im angefochtenen Entscheid (E. 11) überzeugend dargelegt, warum diesbezüglich keine Verletzung des Gebots der Rechtsgleichheit vorliegt.
Auch aus der neu vor dem Bundesgericht vorgetragenen Begründung ergibt sich keine Verletzung von <ref-law>: Vorab geht es im vorliegenden Fall um die gemeinsame Nutzung von dreistelligen Kurznummern, bei den Auskunftsdiensten (18xy) bzw. Helikopterrettungsdiensten (1414 und 1415) hingegen um vierstellige Nummernkategorien. Bei den Auskunftsdiensten wird sodann der angebotene Dienst direkt und abschliessend über die Nummer erbracht, während Pannendienste über die zugeteilte Nummer vermittelt, aber nicht erbracht werden. Wie das BAKOM in seiner Vernehmlassung vom 14. September 2011 zu Recht ausführt, kann im Bereich der Auskunftsdienste der Wettbewerb nur spielen, wenn jeder Anbieter über eine eigene Nummer verfügt. Beim Pannendienst bildet die Vermittlung des Dienstes über eine Telefonnummer hingegen nur eine Durchgangsstufe für die Inanspruchnahme der eigentlichen Dienstleistung. Auch bei den Helikopterrettungsdiensten liegen wesentliche Unterschiede zu den Pannendiensten vor: So wird der Dienst praktisch ausschliesslich im Alpen- und Voralpengebiet von zwei Gesellschaften erbracht. Der Markt ist relativ statisch und war zudem bei Eingang der Gesuche bereits geografisch aufgeteilt. Demgegenüber bringt der Beschwerdeführer selber vor, dass ein Szenario von mehr als zehn Interessentinnen für eine Kurznummer für Pannendienste realistisch sei, so dass eine Erweiterung der Zusatznummer um eine Ziffer bereits nicht mehr ausreichen würde. Es bestehen damit sachliche Gründe für eine unterschiedliche Behandlung von Pannendiensten gegenüber Auskunfts- oder Helikopterrettungsdiensten.
Hinzu kommt, dass der Beschwerdeführer nicht etwa beantragt, es seien den verschiedenen Pannendiensten je eigene vier- oder allenfalls fünfstellige Kurznummern zuzuteilen, sondern es sei ihm weiterhin die alleinige Nutzung der Nummer 140 zu bewilligen. Dadurch würde aber der Beschwerdeführer in einer rechtsungleichen Weise gegenüber anderen Pannendiensten bevorzugt, weil diesen infolge der begrenzten Zahl dreistelliger Nummern kaum mehr eine solche zugeteilt werden könnte.
5. 5.1 Der Beschwerdeführer macht weiter geltend, die Beschwerdegegnerin erfülle die Voraussetzungen von <ref-law> nicht. Die Feststellungen, wonach die Beschwerdegegnerin die Voraussetzungen für die Erteilung einer Kurznummer erfülle, basierten auf ungenügenden und das rechtliche Gehör verletzenden Sachverhaltsfeststellungen und sei damit Resultat einer formellen Rechtsverweigerung. Die Vorinstanzen hätten nicht genügend geprüft, ob die Beschwerdegegnerin im Sinne von <ref-law> das "unverzügliche Eingreifen vor Ort" sicherstellen könne und ob es sich bei den Arbeitnehmenden der Partnerbetriebe der Beschwerdegegnerin um "Fachleute" handle.
5.2 Die Ausführungen des Beschwerdeführers überzeugen nicht: Die Vorinstanzen haben - im Rahmen der zur Verfügung stehenden Möglichkeiten - durchaus geprüft, ob die Voraussetzungen von <ref-law> erfüllt sind und diese Frage mit nachvollziehbaren Argumenten bejaht. So ist der Schluss der Vorinstanz nicht zu beanstanden, für das Kriterium "unverzügliches Eingreifen vor Ort" spiele es keine Rolle, ob die Dienstleistung mit einer eigenen Flotte oder durch Mitarbeitende eines Drittunternehmens erbracht wird (vgl. angefochtener Entscheid E. 9.3). Ebenso kann in Übereinstimmung mit der Vorinstanz festgestellt werden, dass hier einzig entscheidend ist, ob die Hilfe sofort erbracht wird. Der Beschwerdeführer bringt denn auch nichts vor, was darauf hindeuten würde, dass die Beschwerdegegnerin nicht in der Lage sein sollte, unverzüglich vor Ort einzugreifen. Er begnügt sich mit dem pauschalen Vorwurf der offensichtlich unrichtigen Sachverhaltsfeststellung, der hier jedoch ins Leere zielt.
Das Gleiche gilt für die Rüge, das Tatbestandsmerkmal der "Fachleute" im Sinne von <ref-law> sei nicht erfüllt: Wie schon die Vorinstanz verbindlich festgestellt hat, sind die Vertragspartner der Beschwerdegegnerin professionell im Bereich der Motorfahrzeugreparaturen tätig und verfügen damit über genügendes Fachwissen im fraglichen Bereich (vgl. angefochtener Entscheid E. 10.3). Damit ist der Schluss, diese gelten als Fachleute im Sinne von <ref-law> nicht zu beanstanden. Der Vorwurf, die Vorinstanz habe das Tatbestandsmerkmal der Fachleute "ins Beliebige ausgedehnt", trifft nicht zu. Ebenso wenig hat die Vorinstanz eine Gehörsverletzung oder eine formelle Rechtsverweigerung begangen.
6. 6.1 Schliesslich rügt der Beschwerdeführer "weitere Rechtsfehler": Die Vorinstanz habe bei der Anwendung von <ref-law> die Tatbestandsmerkmale des "allgemeinen Nutzens" sowie des "Pannendienstes" falsch ausgelegt und deren Vorliegen zu Unrecht bejaht und somit Bundesrecht verletzt.
6.2 Der Beschwerdeführer wiederholt hier im Wesentlichen seine bereits vor der Vorinstanz gemachten Ausführungen, so dass die Beschwerde den Begründungsanforderungen (vgl. E. 1.4 hiervor) kaum zu genügen vermag. Somit kann diesbezüglich auf die zutreffenden Erwägungen im angefochtenen Entscheid (E. 7 und 8) verwiesen werden: Der Schluss der Vorinstanz, die Erbringung eines Pannendienstes, wie ihn die Beschwerdegegnerin betreibt, stelle eine Dienstleistung von allgemeinem Nutzen dar (E. 7.4) ist dabei ebenso wenig zu beanstanden wie deren Ausführungen zum Pannendienst, wonach die Weiterfahrquote nicht alleine entscheidend sei (E. 8.4). Insbesondere schliessen Gewinnstrebigkeit und die Rechtsform einer AG nicht aus, dass ein Pannendienst von allgemeinem Nutzen im Sinne von <ref-law> sein kann.
7. Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens (<ref-law>). Zudem schuldet er der Beschwerdegegnerin eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat der Beschwerdegegnerin für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Bundesverwaltungsgericht, Abteilung I, schriftlich mitgeteilt.
Lausanne, 12. Dezember 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger