There are two ways to add items to the context menu. I'm not sure why you don't want to use the registry, because it is the easiest method. And you can have your installer automatically add or remove the registry keys if you want. Both will use the registry anyway, since registering a Shell Extension involves adding registry keys.
Registry
This method is easy since it comes down to adding some registry keys. The downside is that you can't put any logic in it. You can read about it here. You get a bit more control if you are using DDE to execute the menu items. See here for a DDE example.
Shell Extension
This method is a bit more work, but you can completely control the context menu from code. You would have to write a DLL, implement IContextMenu (or others) and register the dll with Windows Explorer. You can read about it here and see here for an example. You could also check out 3rd party libraries like ContextMenu.