Если загранпаспорт обращайтесь в консульство установленным порядком - при этом Вы должны легально проживать в Канаде.
http://www.toronto.mid.ru/
Внутренний паспорт - никак, надо ехать в Россию

Если паспорт утерян, то сначало нужно заявить об утере в полицию. У них для этого есть специальные формы. Стоит это удовольствие 25 долларов. Обязательно возьмите визитку констебля, который примет у вас заявление.
Если вы не сильно хотите чтобы консультсво видело все штампы в вашем паспорте и имело представление как вы долго находитесь в Канаде, тогда забудьте паспорт в штанах и постирайте штаны. С нашими соотечественниками это часто случается.
Дальше на сайте указаном выше нужно заполнить две формы и в электронном виде переслать их в консульство. После чего они вам назначат appointment по поводу выдачи паспорта.
Как быстро вы получите новый паспорт зависит от многих обстоятельств. Например, состоите ли вы уже на консульском учете в Торонто, как срочно вам нужен паспорт и т.п. По нормальному это занимает около четырех месяцев.

На сайте генконсульства написано:

Внимание! Для оформления нового загранпаспорта необходимо иметь действующий российский загранпаспорт либо действующий российский внутренний паспорт. Если оба паспорта недействительны и Вы не состоите на консульском учете в Генконсульстве, Вам необходимо подавать документы в Генконсульство на подтверждение наличия российского гражданства. В этом случае только после получения подтверждения из России, можно будет подать документы на оформление нового загранпаспорта.

Я понимаю из этого, что даже если паспорт есть, но он просрочен, все равно придется начинать с процедуры подтверждения наличия российского гражданства?

Придется. Это будет стоить дополнительные 72 доллара.

Спасибо всем за информацию.
Очень хочется узнать сколько составляет консульский сбор в долларах Канады за обмен загран паспорта?