Lots of options.
Most online email folks put some fairly sophisticated contact
management into their email tools. Fastmail.fm, Yahoo email, Gmail,
etc... all let you enter more info for a contact than just an email
address.
For a more elegant solution, you can always get a .Mac account and
sync your address book. Just log into .Mac and you'll have all your
contacts and can add/edit them as needed!
Lastly, you could look at a cross platform contacts manager such as
Now Contact to handle your stuff and set up a synchronization server.
--Nik