Here's a great post by Milo Yiannopoulos proposing some occasionally tongue-in-cheek tips for startups to get attention early on in their life, when they can't afford to spend much on PR.
Prey on a journalist's weak spot. Taking a journalist for lunch is one of the most effective ways to get coverage. It's time consuming, it's borderline immoral, but it's true. That's because we're all broke and consequently don't eat out much. Be strategic about who you approach, find our what they like (eavesdropping on their Twitter feed is a good way to do this) and drop them an invitation. There are other ways you can tickle a journo's sweet spot too: find out what their hobbies are and tailor your communications accordingly. The Jedi move is flattery: no journalist is immune to the "I love your stuff" line. Even if they don't believe it's entirely sincere, they tend to respond to it anyway.
One thing that I've learned about early startup PR is, if you're paying someone to do your PR at that stage, you're doing it wrong. As Milo suggests, be creative, be controversial, be novel and opinionated, and if you can draw in some kind of sex or celebrity angle, even better.
If you read this far, you should follow me on twitter here.