One way around this would be to provide your program in SWC form, along with a Makefile and a pointer to the Flex SDK tools. The user is then free to link up a new version of your program with a different SWC for the LGPL'd library you want to use.
Bottom line, whatever way you choose, the primary freedom you need to preserve to comply with the LGPL is that of your users to swap in new versions of the LGPL'd library at any time of their choosing. It sounds like RSLs can't do what you want, and your users don't get the freedom they were promised by the LGPL'd library's copyright holder with any solution involving your server. (e.g. You can't just let users upload a .swc for you to relink into their special hosted version of your Flex app, since that puts your users at your mercy: if your server breaks or you go away, your users' ability to take advantage of their promised freedom under the LGPL also goes away.) You either have to give your end users the freedom to relink the program themselves, or don't use LGPL'd code.
Maybe this sounds unfair to you, but this is exactly the sort of thing the library's copyright holder had in mind when he chose the LGPL.