Salut Mathieu,
J'ai eu le même soucis et devais me rendre aux USA tout comme toi : Voici mes démarches :
J'ai été à la police pour déposer une plainte et avoir une preuve de mon vol (pour refaire passeport et visa)
1- J'ai refait mon passeport tout comme toi, et reçu à temps avant le départ
2- J'ai imprimé ma lettre d'introduction
3- J'avais une photo de mon ancien VISA
4- J'ai fait un AVE (au cas où)
5- Par sécurité, j'ai imprimé des preuve de ma residence (contrat de location appart, carte bancaire etc...) mais vraiment pas eu besoin !!!
6- J'ai fait une demande de renouvellement de Visa sur le site en payant 30$ (mais il fallait attendre 1 mois pour l'obtenir)
A l'ALLER : je n'ai eu aucun pb excepté pour retirer mon billet à la borne de check in. Un agent m'a aidé, je lui ai expliqué la situation,m'a fait qq blagues et a réussi à me débloquer pour retirer mon billet .
Je suis passée à la douane sans soucis, en répondant aux questions et procédures d'usages (passeport, empreinte, ESTA...) ... J'ai donc pris l'avion sans soucis et profiter de mon séjour à New York
AU RETOUR : Lors de mon retour vers le Canada, je suis passée à la douane canadienne, et j'ai expliqué au douanier ma situation, en lui montrant ma lettre d'introduction. Très gentiment, Il m'a indiqué le bureau d'immigration... J'y suis allée , j'ai patienté (un peu ...30 min) et là une agent de l'immigration m'a reçu, elle a pris ma lettre d'introduction, mon passeport et le numero de plainte (pour le vol du visa, passeport etc.) , m'a retrouvé dans leur base et m'a proposé de réediter mon visa dans la foulée...

Mais comme j'avais déjà effectué la demande, elle n'a pas pu le faire alors elle m'a tamponnée sur mon passeport "le visa avec la date correspondant à mon pvt" pour que je sois tranquille ! ^^
Hey voilà

Bon courage ^^