Here's a version in C. It's different in that it produces the results in a different order, it doesn't use recursion, and it doesn't construct temporary lists. Instead, it uses an encoding for a choice.
Oh, it uses C style array initialization.

---

static char
	*sub0[] = {"small", "medium", "large", 0},
	*sub1[] = {"vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger", 0},
	*sub2[] = {"cone", "cup", 0},
	**menu[] = {sub0, sub1, sub2, 0};

static int
lgth(char *sub[])
{	int n = 0;
	while (*sub++)
		n++;
	return n;
}

static int
poss(char **menu[])
{	int n = 1;
	while (*menu)
		n *= lgth(*menu++);
	return n;
}

static int
choices(char **menu[])
{	int n = poss(menu);
	while (0<=--n)
	{	char ***m = menu;
		int i = n;
		while (*m)
		{	char **s = *m++;
			int l = lgth(s);
			printf(" %s",s[i%l]);
			i /= l;
		}
		printf("\n");
	}
	return n;
}

int	main(int argc, char *argv[])	{ choices(menu); return 0; }

Here it is in OCaml (http://caml.inria.fr/):

let rec comb = function
  | [] -> [[]]
  | x :: tl -> List.concat(List.map (fun n -> List.map (fun l -> n :: l) (comb tl)) x)

The compiler returns the type

val comb : 'a list list -> 'a list list

which is a clear indication that it has the same polymorphism as your C++ version ('a stands for an arbitrary type). You can use it this way:

comb [["small"; "medium"; "large"];
      ["vanilla"; "ultra chocolate"; "rum raisin"; "ginger"];
      ["cone"; "cup"]]

(BTW, I do not think the base case in your Haskell version is correct -- and the case [] is missing.)

combs = map unwords . sequence

It also saves putting spaces in all the strings.
The sequence function is the magic, in the list monad it generates all the combinations.

#!/bin/sh

for a in small medium large; do
  for b in vanilla 'ultra chocolate' lychee 'rum raisin' ginger; do
    for c in cone cup; do
      echo $a $b $c
    done
  done  
done

Here's a java implementation. It's not all that huge ...

import java.util.Arrays;
import java.util.List;

public class IceCream {

    private void build(String sentence, List... components) {
        if (components.length == 1) for(String component : components[0]) 
            System.out.println(sentence + " " + component);
        else {
            List[] subComponents = new List[components.length - 1];
            System.arraycopy(components, 1, subComponents, 0,components.length - 1 );
            for(String component : components[0]) build(sentence + " " + component, subComponents);
        }
    }

    public static void main(String[] args) {
        new IceCream().build("", Arrays.asList("small","medium","large"),
                                 Arrays.asList("vanilla","ultra chocolate","lychee","rum raisin","ginger"),
                                    Arrays.asList("cone","cup"));
    }
}


size = ["Small ", "Medium ", "Large "]
flavour = ["Vanilla", "Ultra Chocolate", "Rum Raisin", "Ginger"]
container = [" Cone", " Cup"]

combs = [i + j + k for i in size for j in flavour for k in container]

for comb in combs:
print comb