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), die als Trustee des C._, amtet.
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 D._ 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 D._ wirtschaftlich berechtigt.
1998 hielt die irische Gesellschaft E._, an der der Beschwerdegegner 1 beteiligt war, 69 % des gesamten Aktienkapitals der D._.
Ungefähr im gleichen Zeitraum kontaktierte die E._ die Anwaltskanzlei der Beschwerdeführer 1 - 3, um die Gesellschaft E._ 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 F._ und ihrer niederländischen Tochtergesellschaft G._ bestehen soll. Dabei war vorgesehen, dass die Aktien der F._ von der H._ für die wirtschaftlich Berechtigten gehalten werden. Die Gesellschaft G._ hielt demnach die Aktien der D._ zugunsten der H._ und damit letztlich für die wirtschaftlich berechtigten Privatpersonen.
In dieser Struktur hielt H._ 100 % der F._, die wiederum 100 % der G._ hielt, der die Aktien von D._ gehörten. Auf dieser Grundlage wurden die Aktien der D._ indirekt von I._, J._, K._, Y._ und dem Beschwerdegegner 1 je zu 20 % gehalten.
In der Folge wurde K._ ausgekauft, womit sich der Anteil der übrigen wirtschaftlich Berechtigten auf je 25 % erhöhte. 2005/2006 erwarb I._ den Anteil von J._, womit sich sein Anteil auf nunmehr 50 % erhöhte.
2005 kam es zwischen I._ 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 D._ verhinderte. Entsprechend konnten der Anwaltskanzlei der Beschwerdeführer 1 - 3 keine gemeinsamen Instruktionen in Bezug auf die Gesellschaft G._ erteilt werden, der die Aktien der D._ gehörten.
A.c Im Jahr 2006 besprachen die an D._ 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 H._ den Beschwerdegegnern ein als "Confirmation of Fiduciary Holdings" bezeichnetes Dokument aus.
Am 11. Januar 2007 schlossen die Gesellschaften H._, F._, G._ und die neu gegründete Gesellschaft L._ eine Vereinbarung ab, nach der die G._ 13'968 Aktien der D._ 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 H._, F._, L._ und D._ sowie den damals von L._ gehaltenen 13'968 D._-Aktien.
Die Beschwerdeführer beantragten im Wesentlichen die Abweisung der Schiedsklage. Eventualiter beantragten sie widerklageweise, die Beschwerdegegner seien zur Zahlung der ausstehenden Honorare zu verurteilen.
B.b Mit Schiedsurteil vom 30. Juni 2011 trat der Einzelschiedsrichter auf die Widerklage der Beschwerdeführer auf Begleichung der ausstehenden Honorare wegen ausgebliebener Einschreibegebühr nicht ein (Dispositiv-Ziff. 1). In der Sache hiess er die detaillierten Auskunftsbegehren der Beschwerdegegner mehrheitlich gut (Dispositiv-Ziff. 2 - 7).
Alle weiteren Begehren wies der Einzelschiedsrichter ab (Dispositiv-Ziff. 8). 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. 9). Im Weiteren wurden die Beschwerdeführer verurteilt, dem Beschwerdegegner 1 Fr. 53'776.-- als Ersatz für die beglichenen Verfahrenskosten und Fr. 100'972.20 für dessen Parteikosten zu bezahlen (Dispositiv-Ziff. 10).
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.

Erwägungen:
1. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
1.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Zürich. Die Beschwerdeführerin 4 und die Beschwerdegegner hatten im massgebenden Zeitpunkt ihren Wohnsitz bzw. Sitz oder ihren gewöhnlichen Aufenthalt nicht in der Schweiz. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
1.2 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
2. Die Beschwerdeführer bringen vor, die Zeugeneinvernahme von Rechtsanwalt M._ sei in Verletzung des rechtlichen Gehörs (<ref-law>) verweigert worden.
2.1 <ref-law> lässt die Anfechtung allein wegen der zwingenden Verfahrensregeln gemäss <ref-law> zu. Danach muss das Schiedsgericht insbesondere den Anspruch der Parteien auf rechtliches Gehör wahren. Dieser entspricht - mit Ausnahme des Anspruchs auf Begründung - dem in <ref-law> gewährleisteten Verfassungsrecht (<ref-ruling> E. 5 S. 37 f.; <ref-ruling> E. 4b S. 243; <ref-ruling> E. 2c S. 578 f.). Die Rechtsprechung leitet daraus insbesondere das Recht der Parteien ab, sich über alle für das Urteil wesentlichen Tatsachen zu äussern, ihren Rechtsstandpunkt zu vertreten, ihre entscheidwesentlichen Sachvorbringen mit tauglichen sowie rechtzeitig und formrichtig offerierten Mitteln zu beweisen, sich an den Verhandlungen zu beteiligen und in die Akten Einsicht zu nehmen (<ref-ruling> E. 5 S. 38; <ref-ruling> E. 2c S. 578 f.; je mit Hinweisen).
Auch im schiedsgerichtlichen Verfahren gilt der Gehörsanspruch nicht unbegrenzt. So ist es dem Schiedsgericht nicht verboten, den Sachverhalt nur aufgrund der als tauglich und erheblich erachteten Beweismittel festzustellen (<ref-ruling> E. 1b S. 389; <ref-ruling> E. 4c S. 644). Das Schiedsgericht kann daher auf eine Beweisabnahme verzichten, wenn der entsprechende Beweisantrag eine nicht rechtserhebliche Tatsache betrifft, wenn das angebotene Beweismittel offensichtlich untauglich ist oder wenn das Gericht aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (vgl. dazu <ref-ruling> E. 5.3; <ref-ruling> E. 2.1 S. 429; <ref-ruling> E. 4a). Die antizipierte Würdigung von Beweisen durch ein internationales Schiedsgericht kann im Beschwerdeverfahren nur unter dem beschränkten Blickwinkel einer Verletzung des Ordre public überprüft werden (Urteile 4A_600/2010 vom 17. März 2011 E. 4.1; 4P.23/2006 vom 27. März 2006 E. 3.1; 4P.114/2003 vom 14. Juli 2003 E. 2.2).
2.2 Die Beschwerdeführer verkennen diese Grundsätze, wenn sie die rechtshilfeweise Einvernahme des Zeugen M._ entgegen den schiedsgerichtlichen Erwägungen als tauglich bezeichnen und die vom Schiedsgericht angeführten Gründe für die verweigerte Zeugeneinvernahme in appellatorischer Weise kritisieren. Der Einzelschiedsrichter hat nach dem Hearing vom 13. Mai 2011 mit Verfügung Nr. 5 vom 6. Juni 2011 unter Verweis auf die anwendbaren Verfahrensbestimmungen erwogen, die Beschwerdeführer hätten ihre Bemühungen, spätestens mit ihrer Duplikschrift schriftliche Zeugenaussagen ("witness statements") von M._ beizubringen, nicht aufgezeigt. Zudem folge aus den Vorbringen der Beschwerdeführer selber, dass der angerufene Zeuge zu einer Aussage bereit gewesen wäre, weshalb es ihnen möglich gewesen wäre, innert Frist zur Replik entweder schriftliche Zeugenaussagen einzureichen oder zumindest Nachweise dafür beizubringen, dass solche Unterlagen trotz entsprechender Bemühungen nicht fristgerecht zu beschaffen waren. Im Weiteren hat der Einzelschiedsrichter die Verweigerung der rechtshilfeweisen Einvernahme in derselben Verfügung damit begründet, dass das Beweismittel nicht tauglich sei, zumal der angerufene Zeuge im Zusammenhang mit dem strittigen Mandatsvertrag weder als Partei noch als Parteivertreter aufgetreten und die Bedeutung sowie der Mechanismus der gemeinschaftlichen Berechtigung ausserdem urkundlich (in Form der Confirmation of Fiduciary Holdings) dokumentiert sei. In einer weiteren Verfügung Nr. 6 vom 14. Juni 2011, mit der ein Wiedererwägungsgesuch der Beschwerdeführer abgewiesen wurde, bekräftigte der Einzelschiedsrichter seine Ansicht, dass dem beantragten Beweismittel die Tauglichkeit abzusprechen sei und wies im Übrigen darauf hin, dass die Beschwerdeführer nicht einmal substantiiert hätten, inwiefern M._ an den massgebenden Vertragsverhandlungen beteiligt gewesen sei und seine Aussagen im Hinblick auf die zur Diskussion stehenden vertraglichen Vereinbarungen von Bedeutung sein könnten.
Die Beschwerdeführer zeigen keine Gehörsverletzung auf, wenn sie sich darauf beschränken, die angeführten Gründe für die Verweigerung der rechtshilfeweisen Einvernahme in appellatorischer Weise zu kritisieren und den schiedsgerichtlichen Erwägungen lediglich ihre eigene Sicht der Dinge sowie ihre Rechtsauffassung hinsichtlich der (angeblich gemeinschaftlichen) Ausübung der Auskunftsrechte entgegenhalten. Ebenso wenig zeigen sie einen gesetzlich vorgesehenen Rügegrund (<ref-law>) auf, wenn sie dem Schiedsgericht willkürliche oder aktenwidrige Sachverhaltsfeststellungen vorwerfen. Von vornherein unbeachtlich sind ihre Ausführungen, soweit sie vor Bundesgericht - in Abweichung zu den schiedsgerichtlichen Feststellungen - nunmehr vorbringen (vgl. <ref-law>), der angerufene Zeuge sei an den Verhandlungen zum Abschluss der Mandatsverträge mit den vier Berechtigten beteiligt gewesen. Dass die vorweggenommene Beweiswürdigung des Einzelschiedsrichters den Ordre public verletzen würde (<ref-law>), machen die Beschwerdeführer zu Recht nicht geltend.
Der Vorwurf der Gehörsverletzung (<ref-law>) im Zusammenhang mit der beantragten rechtshilfeweisen Zeugeneinvernahme von M._ ist nicht gerechtfertigt.
3. 3.1 Die Beschwerdeführer behaupten unter dem Titel "Verletzung rechtlich geschützter Positionen Dritter" die fehlende Zuständigkeit des Schiedsgerichts (<ref-law>) sowie eine Verletzung des Ordre public (<ref-law>).
Inwiefern ein Beschwerdegrund nach Art. 190 Abs. 2 lit. b und e IPRG gegeben sein soll, legen die Beschwerdeführer jedoch mit keinem Wort dar. Damit verfehlen sie die gesetzlichen Begründungsanforderungen (<ref-law>). Sie zeigen weder eine Verletzung der Zuständigkeitsvorschriften noch des Ordre public auf, wenn sie dem Schiedsgericht im Zusammenhang mit dessen Erwägungen zur Einschränkung der auftragsrechtlichen Auskunftspflicht durch das Anwaltsgeheimnis vorwerfen, die schiedsgerichtlichen Ausführungen seien "nicht mehr nachvollziehbar bzw. schlicht rechtswidrig und willkürlich". Abgesehen davon, dass sich die Beschwerdeführer über weite Strecken auf behauptete Sachverhaltselemente berufen, die sich dem angefochtenen Entscheid nicht entnehmen lassen (vgl. <ref-law>) oder erst nach dem Schiedsentscheid zugetragen haben (vgl. <ref-law>), kritisieren sie richtig besehen lediglich in unzulässiger Weise die Erwägungen des angefochtenen Entscheids, mit denen der Einzelschiedsrichter die auf das Anwaltsgeheimnis gestützten Einwände der Beschwerdeführer gegen ihre auftragsrechtliche Auskunftspflicht entkräftet.
Die Vorbringen der Beschwerdeführer stossen ins Leere.
3.2 Keine Verletzung des Orde public (<ref-law>) zeigen die Beschwerdeführer auf, wenn sie die schiedsgerichtlichen Feststellungen zu den Funktionen des Beschwerdeführers 2 als falsch und aktenwidrig bezeichnen.
Ebenso wenig zeigen sie einen gesetzlich vorgesehenen Beschwerdegrund auf, indem sie beanstanden, der angefochtene Entscheid lasse jegliche Begründung vermissen, weshalb die Beschwerdeführer 1 - 3 auskunftspflichtig sein sollen. Nach der bundesgerichtlichen Rechtsprechung lässt sich aus <ref-law> kein Anspruch auf Begründung ableiten (<ref-ruling> E. 6.1 S. 187 f. mit Hinweisen).
3.3 Die gesetzlichen Begründungsanforderungen (<ref-law>) verfehlen auch die mit "Keine relevanten Tätigkeiten der Beschwerdeführer 2 und 3" überschriebenen Ausführungen in der Beschwerde. Die Beschwerdeführer üben lediglich unter Verweis auf verschiedenste Aktenstücke des Schiedsverfahrens appellatorische Kritik am angefochtenen Entscheid.
4. Die Beschwerdeführer rügen, das Schiedsgericht habe ein Rechtsbegehren unbeurteilt gelassen (<ref-law>).
4.1 Sie machen geltend, die Beschwerdegegner hätten ursprünglich die Herausgabe der von L._ gehaltenen D._-Aktien verlangt. In ihrer Replik hätten die Beschwerdegegner ihr Rechtsbegehren modifiziert und hätten nur noch die Aushändigung von Fotokopien der Aktienzertifikate verlangt, was einem teilweisen Klagerückzug gleichkomme und - aufgrund des bedeutenden Werts der Aktien - bei den Kosten- und Entschädigungsfolgen zugunsten der Beschwerdeführer zu berücksichtigen gewesen wäre.
4.2 Die Rüge geht fehl. Die Beschwerdeführer machen selber geltend, die Beschwerdegegner hätten ihren ursprünglichen Antrag abgeändert, womit das definitive Rechtsbegehren selbst nach der Darstellung in der Beschwerde keine Herausgabe von Aktien umfasste. Dieses Begehren wurde vom Einzelschiedsrichter beurteilt, weshalb keine Rede davon sein kann, er habe Rechtsbegehren unbeurteilt gelassen. Ob die Abänderung des Rechtsbegehrens seitens der Beschwerdegegner zulässig war, ob diese als Klageänderung oder - wie die Beschwerdeführer behaupten - als Klagerückzug zu beurteilen und welche Auswirkungen sie auf die Kosten- und Entschädigungsfolgen zeitigte, richtete sich nach der anwendbaren Schiedsordnung. Indem sich die Beschwerdeführer auf den Standpunkt stellen, die Änderung hätte zu einer abweichenden Kosten- und Entschädigungsfolge führen müssen, behaupten sie lediglich eine unzutreffende Anwendung von Verfahrensvorschriften, zeigen jedoch keinen in <ref-law> vorgesehenen Beschwerdegrund auf.
Abgesehen davon trifft die Behauptung, die Beschwerdegegner hätten zunächst die Herausgabe der von L._ gehaltenen D._-Aktien verlangt, nicht zu. Vielmehr hatten die Beschwerdegegner bereits in ihrer Schiedsklage vom 31. August 2011 ausdrücklich klargestellt, worauf sie in der Beschwerdeantwort zu Recht hinweisen, dass das Schiedsverfahren einzig die Rechenschaftsablegung durch die Beschwerdeführer betreffe, während die Übertragung der D._-Aktien nicht Gegenstand des Verfahrens sei. Damit stossen auch die entsprechenden Vorbringen zu den Kosten- und Entschädigungsfolgen ins Leere, die mit dem Rückzug des angeblichen Begehrens auf Herausgabe der Aktien begründet werden. Einmal mehr zeigen die Beschwerdeführer keine Gehörsverletzung auf, wenn sie dem Schiedsgericht vorwerfen, es habe die Bezifferung des Streitwerts ungenügend begründet (vgl. <ref-ruling> E. 6.1 S. 187 f. mit Hinweisen), und sie gestützt darauf einen höheren Streitwert behaupten.
Der Vorwurf, das Schiedsgericht habe Rechtsbegehren unbeurteilt gelassen (<ref-law>), ist nicht stichhaltig.
Den weiteren Ausführungen in der Beschwerde zu den Kosten- und Entschädigungsfolgen lassen sich keine hinreichend begründeten Rügen entnehmen. Auch darin kritisieren die Beschwerdeführer bloss in unzulässiger Weise die schiedsgerichtliche Festlegung des Streitwerts sowie die Kosten- und Entschädigungsfolgen und werfen dem Schiedsgericht Willkür vor, ohne einen zulässigen Beschwerdegrund aufzuzeigen.
5. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 10'000.-- werden den Beschwerdeführern (unter solidarischer Haftung und intern zu je einem Viertel) auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegner für das bundesgerichtliche Verfahren (unter solidarischer Haftung und intern zu je einem Viertel) mit insgesamt Fr. 12'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Schiedsgericht der Zürcher Handelskammer schriftlich mitgeteilt.
Lausanne, 23. Januar 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann