Каковы правила, регулирующие постоянство возвращаемого значения `operator*` для InputIterator и OutputIterator?

Иными словами, разрешает ли константный итератор изменяемый доступ к базовому контейнеру?

Да. Итератор const не является итератором const; то, что есть const, есть само по себе, а не объект, на который оно указывает. (Это аналог указателя const, то есть T* const или const std::unique_ptr<T>.)

Или определение const_iterator::reference должно быть T& без const?

Он должен вернуть const T&. const_iterator является итератором для const; это означает, что то, на что он указывает, не должно быть разрешено изменять. (Это аналог указателя на const, то есть const T* или std::unique_ptr<const T>.)

Какие типы следует использовать для iterator::reference и const_iterator::reference?

Если вы хотите узнать, какой тип следует присвоить своим типам итераторов (iterator::reference, iterator::pointer и т. д.), вы можете попробовать имитировать то, что делает std::vector, следующая программа после компиляции расскажет вам все, что вам нужно знать (демонстрация в реальном времени)

#include <vector>

template <typename...>
struct WhichType;

int main() {
    auto vec = std::vector<int>{};
    WhichType<typename decltype(vec.begin())::difference_type>{};
    WhichType<typename decltype(vec.begin())::value_type>{};
    WhichType<typename decltype(vec.begin())::pointer>{};
    WhichType<typename decltype(vec.begin())::reference>{};
    WhichType<typename decltype(vec.begin())::iterator_category>{};

    WhichType<typename decltype(vec.cbegin())::difference_type>{};
    WhichType<typename decltype(vec.cbegin())::value_type>{};
    WhichType<typename decltype(vec.cbegin())::pointer>{};
    WhichType<typename decltype(vec.cbegin())::reference>{};
    WhichType<typename decltype(vec.cbegin())::iterator_category>{};
}

какие типы должен возвращать оператор* для итератора, константного итератора и const_iterator?

operator* для обычных итераторов, отличных от const_, должна возвращать изменяемую ссылку на базовый тип, в этом нет двусмысленности, если семантика контейнера это допускает. Например, итераторы std::map возвращают постоянные ссылки на тип ключа, потому что ключ не должен изменяться в std::map (см. https://stackoverflow.com/a/32510343/5501675)

const iterator передает то же значение, что и T* const, const std::unique_ptr<int>, они представляют константные указатели на неконстантные данные. Таким образом, вы можете использовать указатель для изменения данных, на которые он указывает, но вы не можете изменить сам указатель. В этом случае итератор действует как указатель. Таким образом, вы не можете изменить итератор, но вы можете изменить то, на что он указывает (демонстрация в реальном времени)

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

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

Что касается того, какие typedefs он должен иметь, первый пример кода при компиляции должен сказать вам, что

разрешает ли итератор const изменяемый доступ к базовому контейнеру?

Да, если есть контейнер. Например, std::vector<int> разрешает, тогда как std::map<int, int> не разрешает изменяемый доступ к своим типам ключей.

Или определение const_iterator::reference должно быть T& без const?

Посмотрите живую демонстрацию выше, когда вы скомпилируете код, вы увидите, что это const T&