If these are utilityish methods that don't actually need a real blessed object, then:

package Foo::Utils {
   sub frobnicate {
      shift; # ignore invocant
      print "frobnicating!\n";
   }
}

...; # some time later

my $utils = "Foo::Utils";  # no need for a constructor

...; # some time later

$utils->frobincate;        # call as a class method
[download]

That said, writing a constructor isn't hard:

package Foo::Utils {
   sub new { bless [], shift }
   sub frobnicate {
      shift; # ignore invocant
      print "frobnicating!\n";
   }
}
[download]

Or even easier:

package Foo::Utils {
   use Moo;
   sub frobnicate {
      shift; # ignore invocant
      print "frobnicating!\n";
   }
}
[download]