На каком основании можно получить регистрацию в другом городе?

В зависимости, что вам нужно: «регистрация по месту жительства» или «регистрация по месту пребывания» .
Согласно ст. 6 Закона РФ "О праве граждан Российской Федерации на свободу передвижения, выбор места пребывания и жительства в пределах Российской Федерации" Гражданин РФ, изменивший место жительства, обязан не позднее семи дней со дня прибытия на новое место жительства обратиться к должностному лицу, ответственному за регистрацию, с заявлением по установленной форме. При этом предъявляются:
паспорт или иной заменяющий его документ, удостоверяющий личность гражданина;
документ, являющийся основанием для вселения гражданина в жилое помещение (ордер, договор, заявление лица, предоставившего гражданину жилое помещение, или иной документ) , или его надлежаще заверенная копия.
Орган регистрационного учета (отдел УФМС – так называемый «паспортный стол» ) обязан зарегистрировать гражданина по месту жительства не позднее трех дней со дня предъявления им документов на регистрацию.

В соответствии с п. п. 9и 10 «Правил регистрации и снятия граждан Российской Федерации с регистрационного учета по месту пребывания и по месту жительства в пределах Российской Федерации» граждане, прибывшие для временного проживания в жилых помещениях, не являющихся их местом жительства, на срок свыше 90 дней, обязаны по истечении указанного срока обратиться к должностным лицам, ответственным за регистрацию, и представить:
документ, удостоверяющий личность;
заявление установленной формы о регистрации по месту пребывания;
документ, являющийся основанием для временного проживания гражданина в указанном жилом помещении (договоры найма (поднайма) , социального найма жилого помещения или заявление лица, предоставляющего гражданину жилое помещение) .
В случае отсутствия жилищно-эксплуатационных организаций при заселении жилых помещений, принадлежащих на праве собственности гражданам или юридическим лицам, указанные документы представляются этим гражданам или представителю юридического лица, на которого возложены обязанности по контролю за использованием жилых помещений.
Регистрация граждан по месту пребывания в жилых помещениях, не являющихся местом их жительства, осуществляется на срок, определенный по взаимному соглашению:
с нанимателями и всеми совместно проживающими с ними членами их семей, в том числе с временно отсутствующими членами их семей, при условии проживания в домах государственного или муниципального жилого фонда;
с собственниками жилых помещений;
с правлениями жилищно-строительных или жилищных кооперативов, если члены кооперативов не являются собственниками данных жилых помещений.

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

на основании того что собственник (какой то может быть ваш знакомый) с документами о праве собственности на квартиру и с вами под ручку (у вас паспорт должен быть с собой) придет в миграционную службу (в простонародье паспортный стол) и попросит сделать вам регистрацию (и скорее всего он будет согласен только на временную)