Sachverhalt: A. A.a U._ (Beschwerdeführer 1), V._ (Beschwerdeführer 2) und W._ (Beschwerdeführer 3) sind Rechtsanwälte mit gemeinsamer Kanzlei in A._. Die X._ SA (Beschwerdeführerin 4) ist eine nach dem Recht der Britischen Jungferninseln gegründete Gesellschaft (nachfolgend gemeinsam: die Beschwerdeführer). Y._, B._, (Beschwerdegegner 1) ist lettischer Staatsbürger und als Investor und Geschäftsmann tätig; er kontrolliert die Z._ (Beschwerdegegnerin 2), eine nach dem Recht der Britischen Jungferninseln gegründete Gesellschaft (nachfolgend gemeinsam: die Beschwerdegegner). A.b 1990 gehörte die ganze Infrastruktur im Ostseehafen B._ noch staatlich kontrollierten Gesellschaften. Diese wurden in der Folge zum grossen Teil schrittweise privatisiert. 1993 wurde die lettische Gesellschaft C._ gegründet; sie betreibt den Hafen von B._, in dem insbesondere Erdöl und weitere Rohstoffe verschifft werden. Der Beschwerdegegner 1 ist an 6'984 Aktien (entsprechend ca. 14.54 % des gesamten Aktienkapitals) der C._ wirtschaftlich berechtigt. 1998 hielt die irische Gesellschaft D._, an der der Beschwerdegegner 1 beteiligt war, 69 % des gesamten Aktienkapitals der C._. Ungefähr im gleichen Zeitraum kontaktierte die D._ die Anwaltskanzlei der Beschwerdeführer 1 - 3, um die Gesellschaft D._ durch eine Holdingstruktur zu ersetzen. Das Ziel der Umstrukturierung war es, fünf Investoren an der neuen Struktur teilhaben zu lassen. In der Folge wurde vereinbart, dass die neue Holdingstruktur aus E._ und ihrer niederländischen Tochtergesellschaft F._ bestehen soll. Dabei war vorgesehen, dass die Aktien der E._ von der G._ für die wirtschaftlich Berechtigten gehalten werden. Die Gesellschaft F._ hielt demnach die Aktien der C._ zugunsten der G._ und damit letztlich für die wirtschaftlich berechtigten Privatpersonen. In dieser Struktur hielt G._ 100 % der E._, die wiederum 100 % der F._ hielt, der die Aktien von C._ gehörten. Auf dieser Grundlage wurden die Aktien der C._ indirekt von H._, I._, J._, K._ und dem Beschwerdegegner 1 je zu 20 % gehalten. In der Folge wurde J._ ausgekauft, womit sich der Anteil der übrigen wirtschaftlich Berechtigten auf je 25 % erhöhte. 2005/2006 erwarb H._ den Anteil von I._, womit sich sein Anteil auf nunmehr 50 % erhöhte. 2005 kam es zwischen H._ und den weiteren wirtschaftlich Berechtigten zu Unstimmigkeiten. Dies führte zu einer Situation, in der sich je 50 % der Stimmrechte gegenüberstanden, was einen Mehrheitsentscheid der wirtschaftlich Berechtigten hinsichtlich C._ verhinderte. Entsprechend konnten der Anwaltskanzlei der Beschwerdeführer 1 - 3 keine gemeinsamen Instruktionen in Bezug auf die Gesellschaft F._ erteilt werden, der die Aktien der C._ gehörten. A.c Im Jahr 2006 besprachen die an C._ wirtschaftlich Berechtigten die Möglichkeit eines Verkaufs ihrer Beteiligung an einen österreichischen Investor. Zu diesem Zweck verhandelte der Rechtsvertreter der Beschwerdegegner mit dem Beschwerdeführer 1 über die Ausarbeitung entsprechender Dokumente bezüglich der Eigentumsverhältnisse. Am 21. April 2006 stellte die Anwaltskanzlei der Beschwerdeführer 1 - 3 dem Rechtsvertreter der Beschwerdegegner einen Bericht mit verschiedenen Unterlagen zu den erwähnten Gesellschaften zur Verfügung. Am 20. Mai 2006 schlossen die Beschwerdegegner mit den Beschwerdeführern einen Mandatsvertrag ("Mandate Agreement") ab. Am gleichen Tag stellte die G._ den Beschwerdegegnern ein als "Confirmation of Fiduciary Holdings" bezeichnetes Dokument aus. Am 11. Januar 2007 schlossen die Gesellschaften G._, E._, F._ und die neu gegründete Gesellschaft L._ eine Vereinbarung ab, nach der die F._ 13'968 Aktien der C._ an die L._ übertrug. Mit Schreiben vom 9. April 2010 kündigten die Beschwerdegegner den Mandatsvertrag vom 20. Mai 2006 fristlos und verlangten eine vollständige Rechenschaftsablegung über die Tätigkeit der Beschwerdeführer im Rahmen des Auftragsverhältnisses. B. B.a Am 31. August 2010 leiteten die Beschwerdegegner nach den Bestimmungen der Internationalen Schiedsordnung der Schweizerischen Handelskammern (Swiss Rules of International Arbitration) ein Schiedsverfahren gegen die Beschwerdeführer ein. Am 15. November 2010 ernannte die Zürcher Handelskammer den Einzelschiedsrichter. Die Beschwerdegegner stellten verschiedene detaillierte Auskunftsbegehren im Zusammenhang mit dem Mandatsvertrag vom 20. Mai 2006, so insbesondere mit Bezug auf die Gesellschaften G._, E._, L._ und C._ sowie den damals von L._ gehaltenen 13'968 C._-Aktien. Die Beschwerdeführer beantragten, es sei festzustellen, dass die Beschwerdegegnerin 2 das Schiedsverfahren mangels gültiger Vertretung nicht rechtswirksam eingeleitet habe, weshalb das Verfahren in Bezug auf die Beschwerdegegnerin 2 einzustellen sei. In der Sache beantragten die Beschwerdeführer im Wesentlichen die Abweisung der Schiedsklage. Eventualiter beantragten sie unter anderem widerklageweise, die Beschwerdegegner seien zur Zahlung der ausstehenden Honorare zu verurteilen. B.b Mit Schiedsurteil vom 30. Juni 2011 trat der Einzelschiedsrichter mangels gültiger Vertretung auf die Schiedsklage der Beschwerdegegnerin 2 nicht ein (Dispositiv-Ziff. 1). Auf die Widerklage der Beschwerdeführer auf Begleichung der ausstehenden Honorare trat er wegen ausgebliebener Einschreibegebühr ebenfalls nicht ein (Dispositiv-Ziff. 2). In der Sache hiess er die detaillierten Auskunftsbegehren der Beschwerdegegner mehrheitlich gut (Dispositiv-Ziff. 3 - 8). Alle weiteren Begehren wies der Einzelschiedsrichter ab (Dispositiv-Ziff. 9). Die Verfahrenskosten von Fr. 56'800.-- wurden im Umfang von Fr. 55'400.-- aus dem vom Beschwerdegegner 1 geleisteten Kostenvorschuss beglichen und im Umfang von Fr. 1'400.-- den Beschwerdeführern auferlegt (Dispositiv-Ziff. 10). Im Weiteren wurden die Beschwerdeführer verurteilt, dem Beschwerdegegner 1 Fr. 47'640.-- als Ersatz für die beglichenen Verfahrenskosten und Fr. 91'472.-- für dessen Parteikosten zu bezahlen (Dispositiv-Ziff. 11). C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, es sei der Entscheid des Schiedsgerichts der Zürcher Handelskammer vom 30. Juni 2011 aufzuheben. Eventualiter sei der angefochtene Schiedsentscheid mit Bezug auf die Beschwerdeführer 2 und 3, subeventualiter mit Bezug auf den Beschwerdeführer 2, aufzuheben. Sowohl die Beschwerdegegner als auch der Einzelschiedsrichter beantragen die Abweisung der Beschwerde. D. Mit Verfügung vom 3. Oktober 2011 erteilte das Bundesgericht der Beschwerde aufschiebende Wirkung.