I have achieved a solution. I was playing around with it some more and quit and restarted Xcode 5.0.2 without any iOS device attached to my computer. When I selected the target selection button I noticed that there were two iOS devices listed there as seen in the following picture. This suggested to me that it actually was recognizing my 3Gs, just not when I had it connect. My guess is it wasn't recognized because Xcode read that it was running iOS 6.1.3. With Putz1103's suggest that there are two version settings I started digging. Putz1103 was partially correct, and I think you for the inspiration.
Under the "General" tab, three tabs to the left of the "Build Settings" tab when the project is selected in the project navigator there are options that need to be set correctly. Under this tab in the Deployment Info section the Deployment Target needs to be selected to the correct iOS target. After selecting that my 3Gs was selectable as the target, and I was able to build my app on my 3Gs for testing.
Combined with all of my activities outlined in the original question, it is still possible to select a 3Gs as a target for development in Xcode 5.0.2 after Feb 1st 2014.