Вы пытались использовать класс символов с оператором дополнения?
String s1 = "foo : bar";
String s2 = "foo \\: bar";
Pattern p = Pattern.compile("[^\\\\]:");
Matcher m = p.matcher(s1);
if(m.find()) {
System.out.println(m.group());
}
m = p.matcher(s2);
if(m.find()) {
System.out.println(m.group());
}