Конечно все зависит от работодателя и его заинтересованности в новом сотруднике, по закону без трудовой не принимают, но на самом деле можно и какое-то время без нее, а договор потом задним числом подписать, у меня была ситуация хуже, прежний работодатель порвал мою трудовую на моих глазах и ничего страшного, на новом месте новую завели мне.