Well where we are limited with what we can do on that end, like you said we still have the chance to be creative from a marketing perspective.
Our other "non hosting related" sites hold monthly chat parties, where we offer prizes, awards, things like that.. It creates a strong sense of community and keeps people coming back to our site. We are going to do the same thing with Host Junkies. Have a monthly "members only" chat party where we can just get to know one another, throw up some trivia, prizes and things like that. We also have an online radio, so we give away free advertising of some of our clients websites..
You could also award someone with a month's free hosting, or perhaps a gift certificate where they can invite a friend (or obtain a second account themselves) where the first month or two is free.. after that, you have a new paying customer.
It's worked in every other industry we're in.. now, it will be our first time trying this out in the hosting industry, and even though not every webmaster has the time or energy for this type of thing, we expect a good turn-out.. people love the chance to win free stuff, and it gives them the feeling that we really care about our community.