As hippietrail commented above, karaoke in Japan is strictly "boxes", individual rooms seating 4-10 which are rented by the hour.
So it's very much a "friends getting together" activity. I'm not aware of any means for strangers to meet up for "karaoke get-togethers". But with enough time it shouldn't be too difficult to make friends through other activities, and once you have, a group karaoke is almost guaranteed sooner or later.
Even if you are totally alone, it's recently become acceptable, even popular, to "solo karaoke" - rent out a single karaoke box for just yourself and go wild for an hour. Keep in mind though that karaoke shops prohibit customers from visiting strangers' rooms, so don't go in the hopes of meeting someone.
If you go for your last option, just about all hostess bars in places like Roppongi or Kabukicho (Shinjuku) have a karaoke setup where the hostess would be glad to sing with you with appropriate remuneration. Kabukicho can be iffy about letting foreigners in, but Roppongi is basically entirely for foreigners.