You can get a horizontal slimline belt case for your phone. It's not particularly noticeable (unless your phone is huge, like my new S3) and is tailored for the phone, so you're not storing anything else in there that might scratch it, and it's not 'loose' - you can quite happily run with one without having to hold it in with your hand.