Ok, here's a new version. It now generalizes the wrapping, so it's
trivial to add it to new enumerable classes:

class EnumerableProxy < Object
  instance_methods.each { |meth| undef_method(meth) unless meth.to_s =~
/^__/ }

  def initialize(obj, meth, *args)
    @obj = obj
    @meth = meth
    @args = args
  end

  def method_missing(meth, *args, &block)
    @obj.send(@meth, *@args) { |item| item.send meth, *args, &block }
  end
end

module Enumerable
  @@meth_cache = Hash.new
  def self.meth_cache
    @@meth_cache
  end

  # I'm using a string for module_eval instead of a block
  # because using a block necessitates using define_method,
  # and methods created with define_method can't handle a block
  # (because Proc's can't handle blocks)
  def self.wrap_meth(klass, meth)
    meth_sym = meth.to_sym.inspect
    klass.module_eval <<-END
      meth = instance_method(#{meth_sym})
      Enumerable.meth_cache[#{klass.name}] ||= Hash.new
      Enumerable.meth_cache[#{klass.name}][#{meth_sym}] = meth
      def #{meth.to_s}(&blk)
        if blk
          meth = Enumerable.meth_cache[#{klass.name}][#{meth_sym}]
          meth.bind(self).call(&blk)
        else
          EnumerableProxy.new(self, #{meth_sym})
        end
      end
    END
  end

  wrap_meth self, :collect
end

Enumerable.wrap_meth Array, :each
Enumerable.wrap_meth Array, :collect
Enumerable.wrap_meth Array, :collect!

Unfortunately, due to limitations in Proc (documented in the comment
above), I had to use the ugly string form of module_eval.

I also had to use a method cache on Enumerable itself instead of the
individual classes, becuase when I tried it on the individual classes
it wasn't working right (seemed to be accessing Enumerable anyway, so I
was getting cross-class method binding issues).

Be careful when using irb with this, as it the proxy can cause
confusion (since the proxy forwards #inspect along with everything
else). Normally calling #collect without a block is basically the same
as calling #to_a, so "foo".collect normally returns ["foo"]. However,
once you've loaded this code, "foo".collect returns an EnumerableProxy
object, which irb will display as just "foo" because it'll forward the
#inspect message irb sends on to "foo".

Usage of this is pretty easy. Wrap any methods you want with
Enumerable.wrap_method class, :method. Of course it only makes sense on
enumerable methods. Feel free to wrap any more of Enumerable's
built-ins, and any classes you want to use #each with you have to wrap
separately (along with any class-specific implementations of Enumerable
methods, like Array#collect). Interestingly, this seems to work
perfectly fine on destructive methods like Array#collect!.

At this point I'm considering wrapping this up in a gem for
distribution. Any thoughts?