I second the CamelBones suggestion.

The recently released CamelBones 1.0 lets you write stand-alone, redistributable OS X applications (they run on 10.2 to 10.4 without the end user needing to install anything), that you develop with XCode/InterfaceBuilder in the same way as other Cocoa applications. The only difference is that you code in Perl rather than ObjectiveC (you can mix in ObjectiveC if you feel like it).

Of course, you lose the cross-platform capabilities of wxPerl, so this is not an option if you need to support Windows as well.