I dont claim to be an expert by any means, but i have read a few books on small business marketing (internet and non-internet) in my endeavours with my LANparty event. So based on that reading plus my own experiences, here are some thoughts, in no particular order, on promoting the Perl Weekly Newsletter and really any other email newsletter. The reader is encouraged not to just use them as is, but to use them as a starting point for further ideas and experiments to find what works for you.

• Produce content worth reading. Aimed at newbies, intermediate and advanced perl coders. Addressing a variety of uses for perl. Obviously if the steaks are bad or they are always medium rare (yuck), no one is going to come to your steak house - the same with your newsletter.
• Make it as easy as possible to sign up, but be sure to use a confirmation email system.
• Make it as easy as possible to leave, because you always want to leave a good impression.
• Track the incoming hits to the newsletter website. For perl weekly, you will most likely want to use something that takes stats out of the web server logs as many people (including myself) either turn off or disable javascript, or use a webbrowser that doesnt support it. For other newsletters, free javascript based trackers will do fine. The idea is to then use this information to find where people are coming from, then tailor your efforts in the future around these valuable sites.
• Try and get mentioned on big name tech websites (or for non-perl newsletters, significant websites within your topic). Such as slashdot, linux.com, and lwn.net.
• Try to get mentioned on social media by well known persons in the perl community or the wider tech community (or other topic for non-perl newsletters)
• Encourage your subscribers to refer their friends and to post links to your content on their blogs, project websites, frequented forums, irc, social media accounts, conference talks etc. Try and make this as easy and simple as possible, though you shouldnt drown them in "Like this" type icons - the 3 or 4 most popular social media outlets will do just fine.
• Seek and encourage new contributers, then repeated contribution. Make contribution as easy as possible. Perhaps a web form where the person can send in a link to their blog, or via social media - preferably both. People get a buzz when their content is included and will tell all their friends.
• 'Customer of the week' type articles also give people a buzz and bring a human aspect to your content. In this case perhaps 'CPAN author of the week' with a short bio. You can build up a library of these and schedule them so you dont spend ages chasing people each week.
• Use a perl based list manager (this is Perl Weekly Specific) and make a noticable mention of it on the newsletter website. As otherwise you lose street cred. Sympa or Dada mail are both options.
• Come up with non-email subscription methods, like RSS. This also makes it easier for you to get syndicated and thereby gain greater readship.
• Push out mentions of your newsletter releases via social media. Do this automatically to save you time. Twitter and Identi.ca are both easily done. Perhaps make a module for the list manager and contribute it back to the project itself.
• Some people really like stats, major sports exploit this perverse addiction and you can to! Provide stats on (in the case of perl) things like weekly cpan contributions, most downloaded cpan modules, most active perltesters etc etc. This can be generated automatically, so is low cost+time content.
• Seek promotional opportunities where you can include a discount voucher code in your newsletter. This is very non-intrusive and makes your readers very happy. It also makes the promoter very happy as they get very targetted advertising, with a promotional cost that correlates 1:1 with sales. You can of course, seek to get a commission on sales using the revenue to run the newsletter (perl weekly is a personal project) or just pocket the money because you've earned it. In the case of a business, you would just add that to your normal takings.
• Hit the web and promote the newsletter the old fashioned way! Hit usenet and post polite invitations in relevant categories (dont forget to invite them to mention perl weekly in their blogs and websites). Go to freshmeat.net, find the top 20 most active perl projects, then go to their forums, email lists etc and politely invite them to join the list. You should acknowledge them in your newsletter to thank them, something like "Cool Perl Projects that have linked us:"