Faits: A. Au cours de l'année 2009, la société genevoise Z._ Ltd a mandaté A._, associée gérante de V._ Sàrl, pour effectuer des travaux de rénovation dans ses locaux. A._ a confié la réfection des parquets à X._ (ci-après: l'entrepreneur), qui exploite une entreprise en raison individuelle. Celui-ci a adressé deux devis à V._ Sàrl. Après avoir exécuté les travaux et touché des acomptes, l'entrepreneur a fait valoir un solde de 10'743 fr. 80, dans une facture finale qu'il a datée du 21 juillet 2009. Par la suite, Z._ Ltd a confié d'autres travaux à l'entrepreneur, qui les a exécutés. Une facture de 8'265 fr. 50 a été établie le 18 novembre 2009. Le 10 mai 2010, l'entrepreneur a fait notifier à Z._ Ltd un commandement de payer portant sur les montants de 10'743 fr. 80, 8'265 fr. 50 et 2'500 fr. La poursuivie a fait opposition. B. B.a. Le 7 mai 2011, l'entrepreneur a saisi le Tribunal de première instance du canton de Genève d'une demande dirigée contre Z._ Ltd, en concluant au paiement des trois montants précités et à la mainlevée définitive de l'opposition. La défenderesse a déposé une réponse dans laquelle elle concluait à ce que V._ Sàrl [sic!] soit déboutée de toutes ses conclusions. A l'appui de leurs écritures, les parties ont produit des pièces. Elles ont ensuite été convoquées à une audience de débats principaux. Bien que régulièrement citée à comparaître, la défenderesse a fait défaut. Le demandeur a déclaré qu'il confirmait sa demande et considérait la cause en état d'être jugée, tout en relevant que la défenderesse n'avait pas conclu à son déboutement, mais à celui de V._ Sàrl. A l'issue de l'audience, le tribunal a gardé la cause à juger. Par jugement du 4 octobre 2012, le tribunal a admis l'action à raison de 3'256 fr. 70; il a prononcé, à due concurrence, la mainlevée définitive de l'opposition dans la poursuite en cours. Le tribunal a jugé que le solde de la facture du 21 juillet 2009 (10'743 fr. 80) n'était pas dû par la défenderesse. Le demandeur avait fonctionné comme sous-traitant de V._ Sàrl et n'avait aucun lien contractuel avec Z._ Ltd. Quant aux travaux visés par la facture du 18 novembre 2009, ils avaient bel et bien fait l'objet d'un contrat d'entreprise entre le demandeur et la défenderesse, qui devait payer le solde de 3'256 fr. 70. Enfin, le prétendu dommage supplémentaire à l'intérêt moratoire (2'500 fr.) n'était pas établi. B.b. L'entrepreneur a déféré cette décision à la Cour de justice. Celle-ci a jugé recevable la production d'un procès-verbal d'audition établi le 6 juin 2012 dans le cadre d'un procès divisant Z._ Ltd à V._ Sàrl. A._ déclarait avoir indiqué à toutes les entreprises qu'elle agissait en qualité de mandataire de Z._ Ltd. La Cour de justice a rejeté l'appel par arrêt du 26 avril 2013. Elle a considéré que la défenderesse avait fait une erreur de plume sans conséquence en concluant au déboutement de V._ Sàrl. Son défaut aux débats principaux, régi par l'art. 234 al. 1 CPC également en procédure simplifiée, n'emportait pas la fiction d'un acquiescement à la demande, ni celle d'une reconnaissance des faits allégués dans la demande. En l'occurrence, la défenderesse avait contesté l'allégation selon laquelle A._ était sa représentante, de sorte que le tribunal ne pouvait pas faire droit à la demande en paiement sans apprécier les pièces produites. La défenderesse avait en outre allégué que les travaux concernés par la première facture étaient entachés de défauts et avait contesté l'inexistence d'un avis des défauts. Les pièces produites ne permettaient pas de trancher ces questions litigieuses. Le demandeur ne disait pas le contraire en dénonçant une violation de son droit à la preuve. Or, un tel grief était infondé, dès lors qu'il avait déclaré en audience que la cause était en état d'être jugée, renonçant ainsi à l'administration de preuves. C. L'entrepreneur (ci-après: le recourant) saisit le Tribunal fédéral d'un recours constitutionnel subsidiaire. A titre principal, il requiert l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité précédente pour qu'elle procède à l'audition de témoins et rende une nouvelle décision. Subsidiairement, il conclut au paiement de 10'743 fr. 80, sous déduction de la somme de 3'785 fr. 90, payée le 25 février 2013. L'intimée Z._ Ltd conclut à l'irrecevabilité du recours, subsidiairement à son rejet. L'autorité précédente se réfère à son arrêt. 