<p>Flex uses by default UTF-8. I have not fount a way to specify a different encoding/charset on the actionscript WebService class.</p>

Ummm, look here:
http://www.adobe.com/devnet/flex/articles/struts_06.html
I think that sample implies that declaring your mxml file as iso-8859-1 might do the trick, but I really don't think so.
I might be wrong but as far as I know the Flash player only handles UTF-8 encoding. I've searched for a link to an official page saying so, but couldn't find it.
If that's the case you either:
a) update the webservice to handle UTF-8 encoding
b) if that's not possible, proxy your call to your own webservice that accepts UTF-8 and then call the actual one.
You might want to give a go to the old system.useCodepage=true trick BUT that didn't use to work when the user was on Linux or Mac, USE WITH CARE!