для какого-то конкретного файла

-----
Эээ... нет... не для конкретного.
Для конкретного ты напишешь решение номер один и оно пойдет в мусорник.
Пиши для любого какой тебе позже представят...

Вы уже на Гитхабе со своим уникальным универсальным решением или даже продаёте свою либу как продукт? Или это никому не надо? )))

Как решать не знаю.

В приведённых вами условиях слишком много неоговорено, поэтому всегда можно не уложиться в отведённое время. Наиболее быстрая задача, как мне кажется, это иметь заранее заготовленный план такого большого XML файла - т.е. где у него с какого адреса или строки что расположено. Или даже разбить этот файл на куски. И при этом нужно заранее знать, куда вставлять - произвольно не означает в случайное место же, а в какой-то определённый участок, примерно положение которого вы знаете? Т.е. по-любому нужно делать инфраструктуру по обработке таких больших файлов - своего рода "базу данных по большим XML". В этом смысле, наверное, проще действительно хранить подобные данные в БД, и не в XML, а XML генерировать по запросу, или периодически и потом кешировать.

Я думаю, что если вы приведёте своё оригинальное решение, как вы успешно справились с этой задачей, на вас куча критики свалится, т.к. решение будет, скорее всего, либо неуниверсальным, либо требовать создание предварительной инфрастуктуры по обработке таких файлов для таких задач.