I like statelessness as a top priority. However I'm not sure how statelessness ever comes into tension w/ coupling. Aren't they mostly orthogonal concerns?
> I'm willing to make it more complex if it reduces coupling.
Complexity = f(Coupling), in my definition. So an increase in coupling results in an increase of complexity. Sounds like you have a different definition of complexity -- I'd love to hear it.
As for complexity, there are many different types. Coupling is a form of complexity, but it's not the only one. Cyclomatic complexity is another and one. Using regular expressions often increases the complexity of code. And one need only look at the spec for any reasonably popular hash function to see a completely different sort of complexity that's not the result of either coupling unique paths through code. The composite of all the different forms of complexity is how I'd define it since they all add to a developers cognitive load.