Somewhat off-topic, but if this worries you get a secured card from your favorite bank or credit union. Typically you deposit $500 into a special savings account, they freeze it, and they give you a card with a $500 credit limit in return. It reports like a normal credit card. After 6 months to a year of responsible use of the card (i.e. buy a stick of gum every 3 months, pay after you receive the statement) they will graduate it into a standard credit card and unfreeze your linked savings account.

You can build credit history fairly fast this way. (Starting today with no history, you can have FICO 800 in about two years without paying a penny in interest, if that really matters to you.)

Everything in finance is negotiable, but you've generally got to work for it. You can convince a bank officer to override the computer and grant you credit -- this is a matter of routine. It isn't as easy as filling in a web form at 3 AM in the morning and having a decision in 15 seconds, but for minor credit lines it shouldn't take much more than a branch visit if you have history with the bank. (I know we're all wonderful snowflakes, but a bank with hundreds of thousands of customers may have run into someone who dislikes debt before.)