going without "without"

I have a problem, and I'm wondering if anyone can offer a
good solution.  As some of you who've been on this list for a while
may recall, I've been on a long-term crusade to eliminate all
prepositions from Tokana, and replace them with other strategies for
expressing relational concepts (such as oblique cases).  The last
preposition to be eliminated - it fought long and hard, but I finally
vanquished it - was the preposition "kun", meaning "with".  The
functions of this preposition have now been taken over by two of the
oblique cases, the instrumental and the comitative (the latter is a
new addition to the language).  The instrumental is used to indicate
tools and other instruments which actually perform the action named
by the verb.  For example:

  Ma     tsitspeh        kopo itan     konomny
  1s.Erg smashed-the.Abs pot  the.Inst hammer-Inst
  "I smashed the pot with the hammer"

  Na      Tsion litkeh      homa  itan     kamalny
  the.Erg John  cut-the.Abs bread the.Inst knife-Inst
  "John cut the bread with the knife"

(Note that the instrumental is also used to indicate concepts like
"through", and "via".  In general, it is used to indicate objects
and locations which act as intermediaries between the actor and
the goal/patient in an action.  E.g., the knife acts as an
intermediary between John and the bread by actually performing
the act of cutting, as a result of John's manipulating it.)

The comitative case (marked by the suffix "-a" or "-ia" on the
noun) is used to indicate a participant who is accompanying
another participant in an action, or an instrument which is
aiding in the performance of an action.  For example:

  Ma    puniei            pule        inak    Tsiona
  I.Erg travelled-the.Dat village-Dat the.Com John-Com
  "I travelled to the village with John"

  Na      luiha     eta  ypena
  the.Erg old.woman walk stick-Com
  "The old woman walks with a stick"

All well and good.  The problem is that I now no longer
have a good way to express "without" in Tokana.  Once I'd
eliminated the preposition "kun" = "with", I had to get rid
of the derived form "tukun" = "without" as well, for the
sake of symmetry.  So now I'm stuck as to what to do instead.

Adding a new case form (the "privative" case?) seems a little
drastic.  I pride myself on the fact that all of the existing
cases in Tokana (there are 6 of them now) are highly
polysemous, each combining various different grammatical
functions in a single form.  It would be a shame to go against
this trend by adding another case form which has only one
specific function - to indicate the absence of an object.

A second option would be to express "without" by negating
the noun phrase in the comitative case, thusly:

  Na      luiha     tun ypena     ietoti
  the.Erg old.woman Neg stick-Com walk-Neg
  "The woman doesn't walk with a stick"
  "It's not with a stick that the woman walks"

However, this seems to convey the wrong meaning: The sentence
seems to imply that the woman walks with SOMETHING, but that
this something happens not to be a stick.  (My instinct is that
"without" means something slightly different from "with" + "not",
or "not" + "with"...  Is that right?)

The only other thing I've been able to think of is to express
"without" periphrastically, using a noun or a verb.  For instance:

  Na      luiha     eta  itak    kloha    ypen
  the.Erg old.woman walk the.Com lack-Com stick
  lit. "The old woman walks with the lack of a stick"

Or:

  Na      luiha     eta  itak    ehotia     ypen
  the.Erg old.woman walk the.Com having-Neg stick
  lit. "The old woman walks [while] not having a stick"

However, these seem a little awkward, and I'm reluctant to go
the periphrastic route until I've exhausted all other
possibilities.

So: Does anyone have any suggestions on what I should do?
I know there are natlangs out there which express the various
functions of "with" using cases.  The Australian language
Warlpiri, for example, has a comitative case which operates
much like the comitative in Tokana:

  Maliki  ka   natuwu-rlajinta parnka-mi
  dog.Abs Pres horse-Com       run-Nonpast
  "The dog is running along with the horse"

Anybody know how such languages express "without"?  How do
people express "without" in their conlangs?  Any help with
this sticky issue would be much appreciated.

Matt.