I find that a standers, one-legged kickstand doesn't work well with a full touring load (as you've found). I used a two-legged stand mounted to the frame just behind the bottom bracket, and while that worked well, it scraped up the frame where the kickstand was mounted.
Touring without a kickstand was my solution for quite some time, until I found the click-stand. It's a kickstand substitute, essentially a modified tent pole with a cradle on the end. It's custom sized by the manufacturer so it'll fit with your bike. It's particularly well-suited to loaded touring bikes, and is much more stable than traditional kickstands. However, It takes a little time to deploy, and I'm not sure it'd work reliably with a load of loose items such as groceries unless they're very tightly packed. (More information, including pictures here.)
However, none of these will let you spin the pedals while the stand is down, unless you have very long chainstays; as far as I know, most bikes, except for cruisers, do not. A kickstand mounted to the rear triangle, just in front of the rear axle, will allow you to spin the wheels while the bike is parked, if you balance the bike on the front wheel and the rear, deployed kickstand. The Greenfield stabilizer kickstand has a good reputation in the touring community. We have one on one of our bikes, a Trek Navigator. It seems stable, but we haven't brought that bike on tour just yet. (With the Greenfield on the bike, I was able to balance the bike with panniers on it, so it looks good.)
Summary: If your frame is particularly sturdy and you're not worried about scratching it, a two-legged kickstand on the chainstays behind the bottom bracket will work best. If this is not the case, a kickstand on the rear triangle would work well for you.