I agree that there isn't really a simple answer. That's part of the reason why I categorize obedience to the state under the whole "not being a stumbling block to others" thing. That means that the laws of men aren't black and white rules that we must follow... it's more about keeping up appearances so that our witness isn't ruined.
Your question, "when does the rebellion become the government?" Is a great and difficult question. It will be very difficult to determine when exactly we've reached that moment. But I think that when the government is seen as the enemy by the culture at large, we will be right to defend ourselves against them.
But then again, I may be wrong. Like you said, the Bible doesn't give clear instruction on these things.