I liked the way it was done in Guild wars, although it needs to be tweaked for single player usage.
In guild wars you had no potions. Every class had some kind of healing spell. (vampiric attack, just a normal healing spell, an enchantment spell that healed you based on the mana used, hex spells that heal you by succesfully casting them on an opponent, ...)
There are so many options for that.
Normally there was no HP recovery but if you avoided combat for a while you would slowly build up HP recovery that heals you faster and faster every few seconds untill you reach full health.
There were also vampiric weapons that slowly drained health but you regained health with every succesfull hit.
Simply put, I don't like potions very much.
