You could always substitute mayo with sour cream or greek yogurt. It won't have the same richness but sometimes I cut my coleslaw with those two things, although I do still use mayo. Hope that helps.

I've used a cilantro-lime-yogurt mix to dress cabbage slaw for tacos with much success.

A popular restaurant here in Southeast Mi uses and Italian dressing. Excellent!

Do a search for "amish slaw dressing" - best way to do slaw imho.

From an old Junior League cookbook, I have a recipe with a dressing of 3 T vinegar, 3 T oil, 3 T sugar, 1 tsp salt, half tsp celery seed, half tsp dry mustard. Add to 4 cups shredded cabbage, 2 shredded carrots, half of a green pepper. You can also add some chopped onion and parsley. I use rice wine vinegar - it's the mildest. Kind of an old Fashioned recipe.

this is a very simple one:

http://food52.com/recipes...

I asked a similar question recently and there were a couple of good possibilities suggested in response that didn't contain mayo: http://www.food52.com/hotline...

Cilantro slaw (only works if you & yours love cilantro, obviously). Shredded cabbage, chopped cilantro (lots), chopped cucumber and chopped red onion. Mix a dressing of lime juice, olive oil, garlic and S&P. Dress right before serving, and adjust seasoning to taste. My favorite on top of a fish taco, and great as a light, refreshing side to all sorts of Mexican dinners.

I mix ranch dressing, lime juice, cumin and coriander . Pour it over cabbage, cilantro, jalepeno. Sometimes I add corn and cheddar as well

Sweet Broccoli Slaw!
1 14-oz Bag Tri-color coleslaw (I use Mann's Brand)
1/2 12-oz Bag Broccoli slaw (I use Mann's Brand)
1 Cup Poppy seed dressing (I use Brianna's)
1/2 Cup Greek yogurt (I use FAGE Total Greek Yogurt)
1 Cup Walnut pieces
1 Cup Dried cranberries
1/4 tsp Garlic sea salt
Pepper to taste
Procedure
1. Combine the Cole Slaw and Broccoli Slaw in a large bowl, set aside.
2. In a separate bowl, mix poppy seed dressing and yogurt; then add the walnut pieces, dried cranberries, sea salt and pepper.
3. Mix well together, dressing and slaw mix. Put in a container, seal well and refrigerate before serving.
Servings
Yield: 1 1/2 Quarts

I would just use Greek yogurt, thinned with a little buttermilk. You could also go a completely different route and make a hot slaw with bacon, using the bacon grease as the oil component of your dressing--hot bacon fat, yellow mustard seeds, apple cider vinegar, brown sugar, salt and pepper.

The slaw in this recipe is fantastic (and it has neither mayo nor dairy)! If you have a food processor with a grating disk, you can whip this up in 3 minutes. I really, really love it! http://food52.com/recipes...

This is my recipe for Asian Cole Slaw. It is a big hit for parties
1 package coleslaw
1 bunch of green onions
1 package beef flavored ramen noodles
½ cup slivered almonds
½ cup sunflower kernels
½ cup oil
1/3 cup rice vinegar
¼ cup sugar or Splenda
Crumble ramen noodles, mix with almonds and sunflower kernels and brown lightly in oven at 350 degrees for a few minutes. Set aside and let cool.
Mix oil, vinegar and sugar and set aside.
Thinly slice green onions and mix with coleslaw. Add flavoring packet from ramen noodles. Toss with dressing. Then toss in the noodle and nut mixture. Serve immediately.

I use pickle juice with a little sugar added. It's very fresh tasting and delicious.