Sachverhalt: A. Am 22. Juli 2013 erliess das Untersuchungsamt St. Gallen einen Strafbefehl wegen Hehlerei gegen X._, der dagegen Einsprache erhob. Das Kreisgericht St. Gallen verfügte am 26. September 2013, der Strafbefehl sei wegen fehlender örtlicher Zuständigkeit nicht gültig. Es wies das Verfahren zur Überweisung an die zuständige Behörde an das Untersuchungsamt St. Gallen zurück und erhob keine Kosten. Dieses überwies es an die Staatsanwaltschaft Zürich-Sihl. Die Staatsanwaltschaft Zürich-Sihl stellte das Verfahren am 4. Februar 2014 ein. Sie nahm die Verfahrenskosten auf die Staatskasse und richtete X._ weder eine Entschädigung noch eine Genugtuung aus. Dagegen erhob X._ Beschwerde. Das Obergericht des Kantons Zürich trat mangels Zuständigkeit nicht auf die Beschwerde von X._ ein. Sein Gesuch um "unentgeltliche Rechtspflege und Verbeiständung" wies es ab, soweit es darauf eintrat, und auferlegte ihm die Gerichtsgebühr. B. X._ beantragt mit Beschwerde in Strafsachen, die Verfügung des Obergerichts sei aufzuheben und die Sache zu neuer Entscheidung an dieses zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung. C. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Stellungnahme verzichtet.