Нет, он не станет не только первым приложением, но даже первым мессенджером, блокировки сервисов уже были (Blackberry Messanger, LINE, Vchat, соцсеть LinkedIn), запреты приложений тоже были (ну, например, вот: https://tjournal.ru/p/no-mein-kampf-for-google-play).
Как именно можно бороться с Telegram - вариантов, в принципе, много - но излагать их, если честно, не очень хочется, чтобы не "подбрасывать идей".
Стоит помнить, что Telegram - продукт массовый, и его блокировка будет, я думаю, более заметной, чем запрет Blackberry Messanger или LinkedIn. Плюс, зная Павла Дурова, можно предположить, что он приложит усилия к тому, чтобы сделать блокировку как можно более трудоемкой, а её обход - максимально простым для пользователей. Поэтому, с большой вероятностью, нас ожидает некоторая война щита и меча.
Роскомпозор полоснет тунца, думается.