This is how it worked in Jelly Bean (4.1.1):
First I went to Sync and made sure that "Google Photos" is off. There is no setting for Picasa, etc.
Then I followed your instructions as follows:
- All (Downloaded and Running were the only other choice)
- Clear Cache
- Clear Data
All of my camera pics and random pics from folders I created remained in Gallery(along the thumbnail images for my videos), but all the picasa albums were gone.