I got into thinking about this question after what happened in the last world cup. Zinedine Zidane, after head-butting Marco Materazzi, apologized for his actions in a French television channel but added that he did not regret his actions.
Zidane apologized for his head-butt but said he did not regret his actions, alleging that Materazzi had insulted both his mother and sister... (Source: BBC News)
I think it seems intuitive at first to think that you cannot be sorry for an action if you don't regret doing it. And also the corollary: You can not regret an action if you are not sorry for it.
In order to make progress, I think it is best to rule out some exceptional cases. Consider a person who is just incapable of producing feelings of regret. This person may be genuinely sorry for what she has done, but for one reason or another, she just may not "feel" any regret over her actions. She may even defend herself by saying that this is not the only misdeed that she does not regret.
On the other hand, there may be other linguistic uses of "I am sorry" that don't necessarily (at least intuitively) imply that the speaker feels regret. Consider that you need to do some action that will leave a person in some hardship but that you must necessarily do. In such a case you may say, "Well I am sorry but there is nothing I can do". Such uses do not carry the apologetic sense that we are after. Therefore, it is okay to consider them irrelevant for our purposes.
Even though it intuitively seems to be the case that being sorry for an action entails regretting it, I think regarding regret we need to make a few distinctions that will serve useful.
Cognitive Regret (CR): Cognitive regret occurs when one realizes that an action one has done in the past is no longer morally permissible in light of new beliefs, new evidence or a new emotional state. This, I think, is roughly equivalent to saying "I am sorry". (As we will see, there are a few surprises lurking though.)
Emotional Regret (ER): Emotional regret is the emotional state one is in after doing an action that one wishes that one hadn't done. It is the raw anger, resentment or dislike one breeds against one's self after an unwanted act.
When I first sat down to write this distinction, my first gut feeling was that ER is an extension of CR, that is to say, only those agents that have CR can have ER. On the contrary, ER alone seems possible. Consider Oedipus. When he inadvertently kills his father and marries his mother, he may have ER, albeit no CR. Or maybe his ER is so strong that he begins to have CR. I don't think such an attitude would be rational though. Suppose that you, otherwise a circumspect and meticulous individual, accidentally bump your hand into a valuable vase and break it. You may have strong ER, whose object is your breaking the vase and not merely the absence of the vase, regarding your action, but a rational agent will not have CR. I think it is coherent to have strong ER and be fully conscious that one shouldn't and doesn't have CR.
Whether CR should always be followed by ER is question that I shall not pursue here. (I am sure virtue theorists would say so and a stoic may disagree.) I shall not pursue this here.
And I think the more interesting question is not whether you can apologize in the absence of ER (quite usual) but whether you can apologize in the absence of CR.
I already mentioned that CR is in some sense equivalent to simply saying "I am sorry". So the absence of a CR and an apology may seem like, "Well I am sorry but I am not really sorry."
I think there is a way to reconcile absence of CR and being apologetic. What we need to realize is that when we do an action, there can be several aspects or properties that are morally relevant to it.
Returning to Zidane's case for instance, Zidane may not have regretted head-butting Marco Materazzi. Nevertheless, he may regret doing so in front of millions and thereby setting up a bad example for kids who look up to him. So while Zidane may be sorry for one aspect of his action - setting up a bad example for his young audience -, he may nevertheless feel that another overriding factor, reacting to an insult, ultimately justifies his action. (I am grateful to my friend bezgin zor for this last point.)