What do you think about exchanging exposure with other startups which has users that are your potential clients?
For example you have a time management app, other startup has a note taking app, the users of both startups can benefit from those applications.
Why not the owners/marketing responsible can discuss and exchange newsletters mentions, tweets, blog reviews and so on? Kinda: I mention you in my newsletter, you mention in yours...
Would you do something like this? Personally I think it's a good idea to grow your user base but I never tried...have you done something like this?
[UPDATE]
I made a LinkedIn private group to implement this idea: http://www.linkedin.com/groups?gid=4765042 where startup owners can post their niche and what type of exposure they want to exchange.