Synthetic loofahs like the poofy ball-looking things? Try Salux nylon washcloths if you haven't already -- you can pick them up in the bath products section at Uwajimaya. They give you a good scrubbing and are very thin - if you put them in a towel and stomp on them they'll be more or less dry. One of those + a few drops of Bronner's peppermint = instant refreshment in limited spaces. I never travel without one, especially if I think I might be staying in a place with a sink and no shower. If you cut one in half lengthwise they pack down to nothing but are still long enough to allow you to scrub your back.
Some people find them a bit rough, but I've used them since early childhood so I wouldn't know about that. You can get different grades in any case.

