Protection coordination of AC microgrids (MGs) is a challenging task since they can operate either in grid-connected or islanded mode which drastically modifies the fault currents. In this context, traditional approaches to protection coordination, that only consider the time multiplier setting (TMS) as a decision variable may no longer be able to guarantee network security. This paper presents a novel approach for protection coordination in AC MGs that incorporates non-standard characteristic features of directional over-current relays (OCRs). Three optimization variables are considered for each relay: TMS, maximum limit of the plug setting multiplier (PSM) and standard characteristic curve (SCC). The proposed model corresponds to a mixed integer non-linear programming problem. Four metaheuristic techniques were implemented for solving the optimal coordination problem, namely: particle swarm optimization (PSO), genetic algorithm (GA), teaching-learning based optimization (TLBO) algorithm and shuffled frog leaping algorithm (SFLA). Numerous tests were run on an IEC MG as well as with the distribution portion of the IEEE 30-bus test system. Both systems incorporate distributed generation (DG) and feature several modes of operation. A comparison was made with other MG protection coordination approaches proposed in the specialized literature. In all cases, the proposed approach found reduced coordination times, evidencing the applicability and efficacy of the proposed approach.