Find the common characters between two strings without using set operations
With your restrictions, yes, that seems fairly idiomatic.  I am not aware of a good bitset implementation yet -- wrapping java.util.BitSet wouldn't work that well, since a clojure version would want to be persistent.  That said, your restrictions are not idiomatic at all.  Presumably, you don't want to use clojure.set/intersection (and completely trivializing the problem), but something like

(defn find-matching-chars [s1 s2]
  (distinct (filter (into #{} s1) s2)))


really would be far more idiomatic.  I could see using something like your BitSet code if find-matching-chars was actually causing significant performance issues, but short of that, some form of collections manipulation really is the idiomatic way to solve this issue.

In all honesty, my probable course in a situation like this would be to build filter and linked lists from scratch if I couldn't use the built-in versions, but at this point, I am probably straying away from idiomatic code myself.