I have one of those nice Rosendahl II watches from http://www.thinkgeek.com/gadgets/watches/7a91/ Other people have noted how one has to be very careful fitting the band to your wrist as it is a destructive procedure. Well, changing the battery isn't easy either, and if you're not careful, also a destructive procedure. After taking the back off, one needs to remove the plastic battery holder, essentially the whole gray thing you see after taking the back off. It is connected in two places (see the red arrows) and one cannot take the battery out without removing it.
Giving one this
Once that is done, one can gently pry off the clip holding the battery.
Assembly, as they say, is the reverse.