Можно ли было свободно перемещаться по территории СССР?

Конечно, можно было перемещаться. Кроме закрытых городов.

Однако не на всякую работу брали без прописки. А чтобы прописаться нужны были основания -- или наличие работы, или родственник прописывал, или еще по какой причине разрешали.

А такие города как Ленинград и Москва вообще практически исключалась возможность приехать и устроиться на работу. Только на определенную, так называемый лимит -- строительство, милиция, дворники. И то, не любой мог устроиться. Т.е., как я тут писал, 

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

Насчет прописки -- как легко было чужому в Ленинграде поселится.  Моя бабушка и её семья жили в Петербурге-Петрограде, переехали туда до революции. Пережили блокаду, воевали на Балтийском флоте, работали на Дороге жизни. После войны бабушка с мамой уехала на целину, как коммунист ответила на призыв партии, бабушка работала там, в Казахстане, фельдшером, а фактически врачом. Так вот вернуться в Ленинград ей не разрешили. Потеряла прописку -- до свидания. То что партия отправила на целину, никого не волнует. Родственники прописали их к себе в Ленобласти, помогли с устройством на работу. Мама поработала на заводе, поступила в университет. Первый отдел тут же вызвал её и задал вопрос -- каким образом, с какой радости у неё прописка появилась? Зачем родственники её прописали?

Я бы отметил еще другой аспект. Вообще, именно сами перемещения были существенно дешевле. Т.е. и самолет, и, тем более поезд, были доступны по цене гораздо более широкому кругу людей. 

И, кстати, билеты на поезда и на самолеты! были не именными и посадка была без документов. На самолеты ввели продажи по паспорту в связи с попытками угонов самолетов в 70-ые.