After attempting the distribution of a command line application via Rubygems I came to the following conclusion: Any application not intended exculsively for Rubyists should not be distributed via Rubygems.
Another option could also be to convert gems (and dependency gems) to deb or rpm packages https://github.com/jordansissel/fpm/wiki/ConvertingGems
As far as I know, the Foreman project utilizes this approach http://deb.theforeman.org/pool/precise/stable/f/foreman/