It's an interesting transitive usage of
go (and similar motion words). It's more common for them to take an adjective ("Nobody leaves my table hungry", "Don't go away mad, just go away") Having a predicate nominative, as in the example, is more poetic and so, less common.
The literal interpretation of "he walked away a free man” is just "he walked away and thereafter was a free man”, but the connotation is one of causality or anti-causality; that is, because or despite of whatever he was walking away from, he was a free man.
He left the casino a wealthy man
I said goodbye a sadder but wiser person.
It's said of litigation that you go in a pig and come
out a sausage