The best way to store drupal Configuration
If you're literally looking for variable storage, then variable_set() and variable_get() are the way to go...during development.  However - that means the variables are stored in the DB rather than the file system which can make deployment a bit painful later on.  From your question, I assume this is what you are trying to avoid.

If you're looking to store sitewide configuration as opposed to just variables, then there are a couple of options.

Features

I know you said you don't want Features, but Features 2.x is actually a MASSIVE improvement over 1.x, so if you've not ooked at it for a while I'd suggest giving it another go.

Disclaimer: I love Features 2.x :-)

Configuration Management

Then there's Configuration Management which is an attempt at working some of the Drupal 8 CMI work to Drupal 7.  It's relatively easy to use, and also pretty easy to extend. 

On another note; Clive is kind of a Configuration Management evangelist - so if you have any difficulties with it then you have a wealth of information here.

Manual

Lastly, you could create a custom module that implements default configuration hooks (such as hook_views_default_view or hook_default_rules_configuration).  A keen eye will notice that these hooks are a key element in getting configuration into Features :-)

Strongarm is also not dependent on Features, so you can utilise the Strongarm API yourself :)

Extra

I tend to use $conf[] in combination with a Git-excluded local.settings.php (see this question for a reason as to how and why) file for storing environment-specific configuration (such as site e-mail - things that might change between environment).