Okay, regarding HB56. The fire around this debate should peter out somewhat, but the dilemma you pose is one I've had to pray, study and find what I believe to be a biblical response to it.
First, let me state why the debate is set to flicker out. Federal law already says exactly and to the word what HB 56 does in terms of making it a crime to harbor, transport or encourage people who are undocumented aliens ("illegal aliens", if you prefer) who one knows or recklessly disregards the truth about as concerning their immigration status. So, for me, the law being what it is on the federal level for many years now, it is more difficult to remain up in arms about what looks like a fresh assault on ministry, which is what your question assumes. I don't say that critically --- I say it having felt incensed and with a knee-jerk need to protect people whom God loves. That is, until I researched it more thoroughly.
What I fully expect to happen is that everything in HB 56 will be deemed unconstitutional as an state law incursion into an area of law so overtaken by federal control that the Supremacy Clause of the Constitution is being violated by the implementation of HB 56 --- EXCEPT where HB 56 implements e-Verify for employers, which is already up to constitutional muster in other federal circuits and really only streamlines what has been the law for more than 20 years with I-9 forms and such. But, I fully expect -- with little or no doubt -- that the U.S. District Court for the Northern District of Alabama, Northern Division (right in Huntsville where you are, Martha) will hold that the stop and examine law enforcement features of HB 56 and its prohibition of harboring/transporting/encouraging illegals are unconstitutional because the Federal government already completely controls that much of immigration law.
Now, what of that Federal regulation? Well, HB 56 mirrors it. Verbatim, substantially. Difference is that it is not being executed and prosecuted in the way in which popular belief locally would imagine it would be if the state law enforcement officers had a crack at it. The lack of enforcement is the reason the states are pushing the issue by passing laws that violate the Supremacy Clause. And, as far as government goes perhaps their reasons are as justifiable as any. But, it is a lot of sound and fury and election positioning. Politics.
My question has morphed into two, now. 1. Why am I not as angry about the Federal impact on ministry as I was about the exactly same worded state law? 2. What happens when government really DOES -- state or federal -- act in ways that most Alabamians of the same mind as you and I believe put the civil government laws at odds with the laws of God?
I would answer #1 only to say that as long as they don't enforce it, it really isn't law. Sure, they will, can and do capriciously apply and enforce laws. Happens every day and everywhere. But, long spaces of time without really doing anything about it has lured people into ignoring the law on paper. We must be ever mindful as the Day of the Lord approaches that the powers that be will not stop in their ongoing campaign to erase the idea of Christ from the planet. So, we should not allow our lack of anger about the law to devolve into a lack of awareness or sense of security about the government. It is what it is, and what it is is opposed to Jesus, period.
I would answer #2 by taking HB 56 and assuming, for argument's sake, that it really is going to be implemented, and that Christians really are going to have to make a choice because -- although it may not occur in this particular context and time -- it is happening with greater frequency and intensity that "spirit of Caesar", as one might call it or what I call the "culture of government", demands sole devotion. A choice has to be made, and if nothing else, HB 56 is an excellent opportunity to teach Christians a lesson about the nature of civil government and why it is important to know what Paul was saying in Romans 13.
So, let us assume, then, for now, that HB 56 is going to be the actual, applied on the ground in all its aspects law of the state of Alabama, and discuss it from there.
I would say that "legal" does not mean "right". It is "legal" for homosexuals to have sex with one another, but is not "right". It is "legal" for them to marry in some states, but it is not "right".
Let's get to the core of the Bible debate. Get a bible and go to Romans 13, but be ready to look at chapter 12 and to flip to parts of Isaiah. Okay, so some trot out Romans 13 and say, "See? Obey the civil laws! Then, you can be 'right' with the law and then it'll be okay for you to receive/do ministry." Here's why that reliance on Romans 13 is misplaced. I concede that my view is a minority view, here, by the way. But, the passage is constantly wretched out of the larger context and used to mean the opposite of Paul's teaching, as I understand him. Let me explain.
Of course, what we're dealing with is the infamous passage in Romans 13 about civil authorities, etc.
"Be subject to" in Rom. 13:1 is used by Paul after he has already laid down a theme of "loving your enemies" in the sense that Jesus described. That is the bed in which Paul lays this pillow in Rom. 13:1. We must begin understanding Paul's point in 13:1 by going back to Rom. 12:14. In fact, as Paul rolls into his "be subject to" statement in 13:1, he assumes that the powers-that-be are evil at the core in the preceding sentence at 12:21 -- "Do not be overcome by evil, but overcome evil with good." That very sentence is also embedded in a very Sermon-on-the-Mount, didactic and imperative type of instruction in how Christians are to live. It is interesting that those instructions include loving enemies, feeding the hungry and helping those who are both needy and opposed to us. THAT is the backdrop of 13:1 and the "be subject to" instruction.
So, in no way does Romans 13:1 teach that "Hey, the government is a legitimate force to be obeyed. Acknowledge it, submit to it, because it is the government." On the contrary, Paul uses the government as Exhibit #1 of who the enemy of Christians really is and instructs us to do the very thing that is most counter-intuitive but is the epitome of losing-life-for-the-sake-of-Jesus'-name: let the enemy rail. Don't resist. Don't counter. Don't try and pull a power play back on it.
Now, as to the part of Romans 13 about government being instituted by God. Here's the deal. We must keep the backdrop in mind and not peel the words out and stick them on present circumstances and make them something they weren't when Paul wrote them.
Paul is an Old Testament scholar. There was no "New Testament" canon yet; in fact, Paul was writing part of the NT in this letter. He knows the lesson Israel learned (or failed to) in 1 Samuel 8 and thereafter -- that God accepts human, civil government as an accomplished fact. He does not establish or ordain in any sense of "approval" or "legitimization" any civil government; the only government now recognized as "legitimate" by God is the church, the body of Christ, ruled over by its Head, Jesus, who is described elsewhere by Paul as the one and only King. (See, 1 Timothy 6:15, wherein Paul says of Jesus that He is "the blessed and only Sovereign, the King of kings and Lord of lords"). Civil, human government is the rejection of the government of God, as illustrated in 1 Sam. 8 and by every government thereafter. If Paul means to say that God legitimizes and approves civil government in Romans 13, then he is lying about Jesus to Timothy and admits of more than one sovereign. But, just as hard-heartedness of humanity lead to the "acceptance" of divorce by God (see, Matthew 19), God has "accepted" or "allowed" human government -- but both are sinful and both are objects of God's scorn, and both (along with everything else) will face a final extinction in the day of wrath. But, that's another topic.
What of these government folks being called "servants of God"? In Isaiah 13, God calls pagan warriors who exercise His judgment on Israel the same thing. Yet, God, through Isaiah, makes plain that even their evil will meet an end: when God is finished using them to do His work in exacting judgment on Israel, He will destroy those pagan warriors, too! (And, that did, in fact, happen. Read Isaiah 10:5-7, 12-13.)
The Assyrian 'government' in Isaiah 10 acted as the Alabama Legislature -- and voters supporting it -- act now: "I have acted in my own might and I have laid my schemes using my own wisdom" -- and that is precisely what God judged of the Assyrians.
Let's look also at Isaiah 45, where God speaks of Cyrus of Persia as God's "Messiah"! That's right. He uses that very lofty word to describe His servant Cyrus whom He would use to allow Israel to return to Jerusalem from captivity in Persia. Paul's use of "servants of God" in Romans 13 is highly informed by these prophetic mentors of his. Government, to Paul, is not a legitimate, God-approved entity. Rather, it is an enemy of the true faith, but one who must be loved in the way Jesus commands to love enemies, and one who is allowed by God (because that's what humans have chosen and keep on choosing, which has huge implications eschatologically, by the way) to deliver the world up to him until that point in time where every knee will bow, in heaven and on earth and under the earth, and every tongue will confess that Jesus Christ is Lord to the glory of God the Father. (See, Philippians 2).
What we owe to those in government is love. They are people. But, we are not to obey and follow their folly when they act in ways that are, in truth and in fact, anti-Christ. That's what HB 56 is, in large part. If we disobey HB 56 by "encouraging" and "transporting" and otherwise doing ministry to illegal Hispanics or other alien residents of Alabama, it isn't a political statement or a power play. It is to glorify God by continuing to do what Jesus did -- minister to the last, least and lost.
I would extend that rationale of government's inherent opposition to Christ to every action it makes. I have never been more skeptical of the ability of anyone to be a Christian and an elected politician because, at bottom of it, selfishness as a candidate and then the actual support by the office holder of the government that is inherently opposed to Christ must happen. In fact, I am seriously shaky on whether a sworn officer of the court who has to give an oath of support and allegiance to that government can continue to be and do both if he calls himself Christian.
My .02 ----- on steroids.

Human government bears the same relation to hell as the church bears to heaven. (David Lipscomb, On Civil Government, 72).