What, historically, was the stance of the Catholic Church about the duty to obey non-Christian governments?

My understanding of history is that: - During the times of the early Roman Empire the stance of the persecuted Christians was that they recognize the authority of the State and the Emperor and obey them, with the only exception of when the State orders them to sin (ie renounce their faith and worship false gods). God's authority is above the authority of the State, however, whenever the authority of the State does not clash with the authority of God then the State must be obeyed. For this reason when the State was condemning early Christians to death for their religious obstinacy then early Christians thought they now had the duty to obey the order of the State, which was to let the executioners kill them; as doing so was not a sin (as opposed to themselves killing others or renouncing faith) early Christians were not even attempting to escape or to rebel, but were obediently letting the State kill them. (This is sometimes brought even in contemporary times by preachers who advocate the doctrine that all people must unconditionally obey secular powers at all times with the only exception of when the secular power orders them to sin.) - However, in Medieval times, the Pope had the authority to free subjects of a king from the duty to obey him by excommunicating him. Excommunication, as far as I understand, is a formal declaration that someone is outside of the Church. Thus, it would seem to me, in Medieval times the Church did not teach that all must always obey the State, however vicious that State might be; to the contrary, Christians had to obey kings only as long as the Pope recognized these Kings were in full communion with the Church. This seems contradictory to me. Am I failing to understand something? Or did the teachings of the Church on that matter indeed change in between of Ancient and Medieval times?