Jolly gerrymandering
R, 938 896  858 952 bytes



function(N,M,m){U="We tried...
"
L=length
A=matrix
W=which
K=sum
S=sample
G=unique
H=function(s,p=s-1){Y=S(c(s-j,s+j,p*(p%%j&gt;0),(s+1)*(s%%j&gt;0)))
Y[Y&gt;0&amp;Y&lt;=k]}
C=function(v,z=W(r==v))K(z%%j&lt;2,z-j&lt;0,(z+j)&gt;k)
m=A(strsplit(m,"")[[1]],1)
i=W(m&lt;0)[1]-1
m=((t(A(m,i+1))[,1:i]&gt;0)-.5)*2
if((K(m)&lt;M&amp;(N-M)&lt;1)|K(m&gt;0)&lt;(3*M))cat(U) else{j=max(1,nrow(m))
k=i*j;w=g=T
while(w&lt;9&amp;g){Z=R=N;Q=M;b=0
r=A(0,j,i)
while(b&lt;9&amp;g){s=W(r&lt;1)
s=s[S(L(s))][1:min(L(s),R)]
r[s]=1:L(s);a=0
while(K(r&lt;1)&gt;0&amp;a&lt;(k^2)){a=a+1
s=S(W(r&gt;0&amp;r&lt;=R),1);p=r[s]
Y=H(s)
Y=Y[r[Y]&lt;1]
if(L(Y)){Y=Y[order(m[Y])]
if(K(m[r==p]&gt;1))r[Y[1]]=p else r[Y[L(Y)]]=p}}
if(a&lt;(k^2)){for(v in 1:R){if(K(m[r==v])&gt;0){r[r==v]=max(k,max(r))+1
Q=Q-1;Z=Z-1}}
if(Q&lt;1){g=F
for(v in 1:R)r[r==v]=max(k,max(r))+1
for(v in G(c(r)))g=g|(K(r==v)&lt;4)|(L(G(r[H(W(r==v))]))+C(v))&lt;3}}
b=b+1;r[r&lt;=R]=0;R=Z}
w=w+1}
if(g)cat(U) else{u=G(c(r))
for(v in 1:L(u))r[r==u[v]]=v
cat(paste(apply(A(LETTERS[r],j,i),1,paste,collapse=""),collapse="
"))}}}


Try it online!

A massive >900 >800 (nope!) >900 bytes solution.
The code works as follows. Let N be the number of electoral districts and M the minimum number of district where 1 wishes to have a majority. 

First, the code randomly assigns N districts to different groups. Next, it randomly expands them, i.e. adds a district to a randomly selected group, ensuring that the district is next to a district already belonging to that group. In the expansion process, it gives precedence to a district with a 1 majority, if the district group is not yet a full 1 majority; if the group is already a certain 1 majority, then it gives precedence to a 0 district. It continues until all districts have been assigned.

Every group where there is a majority for the 1 party is stored, and its districts are locked. If there are at least M groups with a majority of 1, then everything is good and we can print the result we can check whether there are at least 4 districts in each group. If the cutoff of 4 districts is met, then we can happily print the result. Otherwise, the code tries to reassign the districts that are not locked to as many groups as available, i.e. N - #stored-groups.

The codes tries a few times (9 times). If it fails, it resets everything and starts again. It does so for other 9 times before giving up and printing "we tried...".

If the code does not succeed at first, try again a few times. I tuned the number of repetitions such that it can run in TIO under a minute. However if there is a solution, this code can (eventually) find it. The randomness part of the algorithm gives a non-zero probability that, if there is a solution, it can find it. The limited number of trials is the only limiting factor to success. 

EDIT: added the control that no district group can be fully surrounded by just another one, unless the district group has districts on the edge of the given square. I think I missed it at first.