Словник чужомовних слів і термінів (П. Штепа) (1967 + 1977):
- Віце... — під...
- Віцепрезидент — підпрезидент.

Доволі логічно.

Від прийменника "за" (псл. *za). Прийменник має значення "позаду, ззаду; після, потім". Таке значення вспадковане ше з індоєвропейської. Якшо не помиляюся, то якраз від нього походять "замість" (+ заміщати), "заміна" (+ заміняти, замінник), "заступ" (+ заступати, заступник), "заходити", "забігати". Вибрав саме цей через очевидний зв'язок з тим, хто/шо/як/який стоїть позаду, після когось.

Ось приклади прийменника "за" в цьому значенні в дійсній мові:
- Хто працюватиме за мене?
- Я поставлю підпис за тебе.
- За директора нині працює Наталя.
- Завтра ти дзвонитимеш до людей за мене.

*měna —> *měn-o-
Від "міна" (зміна, обмін, заміна).