>клеймо и тату........

Безотносительно привязки именно к "древнему" Риму или Греции, как мне представляется, до 16-17 веков - клеймо и тату не были основным способом закрепления социального статуса (или по крайней мере - не единственным). В конце концов вывести их всегда возможно. Да и технически - клеймить всех подряд и нижестоящих, и пришлых - проблематично, клеймление же всех привелегированных не исключит "подделок".

Более существенное влияние на устойчивость социального (кастового, классового) разделения играл социальный и технологический фактор, а именно - при том развитии технологии, убежать (например из рабства) в одиночку означало на 99% погибнуть. Вспомните легенду: в "древней Греции" - изгнание из города или из общины было страшнее смертной казни, - ибо в большинстве случаев означало ту же смерть, только медленную.
Человек мог выживать только в примерно постоянном сообществе (клан, община, деревня, город) - где все статусы были известны ближайшим соседям и кому-либо самочинно изменить положение было проблематично. Также влияла круговая порука - не отпустят, ибо расплачиваться и получать наказания придется и за беглых земляков. Даже добравшись куда-то в другое обитаемое место - беглец попадал на низшую ступень социальной иерархии, если не нес с собой достаточно ценностей, которые при этом мог защитить от посягательств - что невозможно для одиночки. Исключением могло стать только если беглец обладал умениями-способностями необходимыми в новой местности, и эта ниша не была там занята местными.

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

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

Т.е., вероятность улучшить свой социальный статус было проще неформально (при наличии соответствующих физических или умственных способностей), чем изменить его подделкой или бегством.
(также, как была высокой и вероятность потерять свое положение при несоответствии)
Следовательно, устойчивость социального (кастового, классового) разделения была динамически равновесной в течении длительного времени.

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

РЕМАРКА:
Тогда же, по мере развития технологий появились и такие феномены, как "знатный, но бедный" и "богатый, но бесправный". Что и способствовало порождению череды смут, революций и распаду единой империи.