#Mathematica, 369 bytes, 2765 characters
t[i_]:={Mod[2i,256],Quotient[i,2],BitXor[i,1],BitXor[i,128],0};w[a_,b_]:=Position[t[a],b][[1,1]];g=Graph[Range[0,255],Flatten@Table[Property[i\[DirectedEdge]#,EdgeWeight\[Rule]w[i,#]]&/@Union@t[i],{i,0,255}]];f=FindShortestPath[g,All,All];c=m=0;o=\"\";u[a_,b_]:=(Do[o=o<>ToString[m=1-m],{If[a\[Equal]b,6,w[a,f[a,b][[2]]]]}];m=1-m);Do[While[c\[NotEqual]y,u[c,y];c=f[c,y][[2]]];u[c,c],{y,ToCharacterCode[i]}];o
Ungolfed version:
i = "This is a string, meant to test the effectiveness of your program. Here are some special characters to make matters interesting: Æ Ø ß. How meta! :D";
t[i_] := {Mod[2 i, 256], Quotient[i, 2], BitXor[i, 1], BitXor[i, 128], 0}
w[a_, b_] := Position[t[a], b][[1, 1]]
g = Graph[Range[0, 255],
Flatten@Table[
Property[i \[DirectedEdge] #, EdgeWeight -> w[i, #]] & /@
Union@t[i], {i, 0, 255}]];
f = FindShortestPath[g, All, All]; c = m = 0; o = "";
u[a_, b_] := (Do[
o = o <> ToString[m = 1 - m], {If[a == b, 6, w[a, f[a, b][[2]]]]}];
m = 1 - m;)
Do[While[c != y, u[c, y]; c = f[c, y][[2]]];
u[c, c], {y, ToCharacterCode[i]}];
o