As opposed to general rendering errors (binding invalid textures), controlled crashes (asserts) are good! They're much easier to debug.

Suppose your GraphicsDevice object holds an already deleted pointer to some Texture. While running in debug mode, when an object is being deleted its associated memory is being overwritten with something like BAADF00D. So you just call the method GetName of your invalid Texture object, and in almost all cases one of the two will happen, either you'll get an exception for trying to read an unallocated memory, or you'll get the magic number. Those magic numbers are big, I mean really big, there's no way you're going to allocate billion textures. So you can just make your assert like this (in SetTexture or directly in GetName):

assert(glIsTexture(texture->GetName()) == GL_TRUE);

glIsTexture is not a cheap call, but it's in the assert, so it'll run only in debug mode. If you want to do something similar in release mode, then you can make the check less costly (but also much less precise) by first overwriting the value of m_texture in the destructor with something big and by changing the check to:

if(texture->GetName() > 1<<20) // Or some other magic number
  throw TextureException;

Although a GL implementation isn't obligated to use contiguous numbers, all implementations I've worked with, do it.

As for your other questions. If GraphicsDevice is going to be responsible for deletion, then yes, you'll probably need to hold the object in many places. Though I think it's reasonable enough, because in 99% of cases there should be exactly one object of GraphicsDevice.
Also, planning to match D3D is good, but you need to know what version to target (10 or 11) and where to draw the line. What you want to do is probably closer to 10 than to 11. Targeting for 11 will require more abstraction in some layers, most notably separating the Device from RenderingContext. For instance, creating a texture is a Device operation, while binding a texture is a RenderingContext operation.
I really cannot summarize D3D10/11 in a few lines of text here, but you can use MSDN and the SDK for pointers on how to do it best.

That looks useful for debugging, but how would you rewrite this code so that it doesn't cause the assert to fail?

GraphicsDevice device;
Texture* texture1 = device.CreateTexture(...);
device.SetTexture(texture1);
delete texture1;
Texture* texture2 = device.CreateTexture(...); // device dereferences dangling pointer; crash

Should I just just add a device.SetTexture(NULL) call before deleting the texture1 object? This could become quite tedious in the generic case, with multiple texture units, though. For example, before deleting any texture you would have to do,

for (unsigned i = 0; i < device.GetNumTextureUnits(); ++i) {
    if (device.GetTexture(i) == texture) {
        device.SetTexture(i, NULL);
    }
}

That looks useful for debugging, but how would you rewrite this code so that it doesn't cause the assert to fail?

GraphicsDevice device;
Texture* texture1 = device.CreateTexture(...);
device.SetTexture(texture1);
delete texture1;
Texture* texture2 = device.CreateTexture(...); // device dereferences dangling pointer; crash

This is problematic. Best way to deal with this is to let GraphicsDevice to deallocate the texture (instead of leaving it to Texture). If deallocating currently bound texture, then just reset the texture pointer to NULL.
There's also the option of using one texture unit as a temporary unit for all those things like creating textures. This is less pretty, and leaves you with one unit less, but it'll help minimize the amount of rebinds.

[quote name='max343' timestamp='1356516002' post='5014372']
This is problematic. Best way to deal with this is to let GraphicsDevice to deallocate the texture (instead of leaving it to Texture). If deallocating currently bound texture, then just reset the texture pointer to NULL.
There's also the option of using one texture unit as a temporary unit for all those things like creating textures. This is less pretty, and leaves you with one unit less, but it'll help minimize the amount of rebinds.
[/quote]

Yeah, moving the deallocation function into the GraphicsDevice class is probably the best solution. Reserving one texture unit for modifying/creating textures would work fairly well, but I don't think it's worth losing the extra texture unit, and this approach doesn't extend to other resource types (buffer objects, shaders, FBOs, etc.)

[quote name='beans222' timestamp='1356498994' post='5014334']

Do you really need to create a texture in the middle of a time when the GraphicsDevice will be caring which texture is bound?

[/quote]

This is a good point, but as mhagain says, there likely are some cases where you may need to modify or create resources in the middle of rendering. In any case, I'd prefer a system where you can create resources whenever you want; I think it's exposing an implementation detail if you restrict users to only doing so at the start of a frame.