How do I go about adding a new device for a user without having to connect it to my server via usb? It's really painful the way I'm currently doing it and not very techie.

You'd perform a Wireless Enterprise Activation from the device itself.
Port3101.org - KB13850 - What is the wireless enterprise activation process

Options > Advanced Options > Enterprise Activation

And if i don't have the device?

I know when i got my device right from AT&T as soon as I connected my blackberry to my desktop manager and vpn'd into work, it started the activation....it actually scared me as to how they knew it was on the network. Now, that i co-manage the BES at my site, i'd like to do the same thing.

The user does the Wireless Enterprise Activation form their own device.
You, as the BES admin, just generate/send the activation password.

This is basic admin 101 type stuff. You might want to skim through the admin guide for BES as this is most certainly covered.