You don’t have to use iTunes, but there is no reason not to. It is very user-friendly, and as already mentioned it will happily manage your existing MP3’s and allow you to import new ones from CD’s without even mentioning the Music Store.
As someone else pointed out, no conversion is required. The Shuffle plays MP3’s natively, along with Apple’s proprietary AAC format (used by the Music Store).