**Edit** In my previous answer I took $M$ to be the set of elements with image $\{2,\dots, n\}$ toegther with a random involution. In fact, that answer does not produce a monoid, since the square of an involution is the identity $\text{id}$ which was not an element of the monoid defined. 

Here is a correct answer. Take $M\subset \text{Self}(\{1,\dots, n\})$ to be the set consisting of the identity, and the set of elements that have image in $\{\lfloor n/2\rfloor, \dots, n\}$. Let $\sigma$ be a perfect hash on involutions that are the identity on $\lfloor n/2\rfloor, \dots, n$. Let $M_\sigma$ be the monoid consisting of $M$ and the involution $f_\sigma$ with $\sigma(f_\sigma) = 0,$ if it exists. Then you can check that $M$ is always a monoid, but you can't compute $f_\sigma(1)$ in polynomial time. 

**Note** With the current formulation of your question, it is actually enough to take $M$ to be $\text{id}$ and a random involution determined by a perfect hash. In a previous version, you asked that $M$ be enumerable in a length of time which is polynomial in $|M|,$ and adding in all elements with image $\{\lfloor 1,\dots, n\rfloor\}$ guarantees this.