in theory, yes, absolutely it's possible, using the same principal as sharing via bridged or ICS methods, using the android as the hotspot, etc.
In theory, anything is possible... in reality everything conceivable happens all the time. That said, I have successfully tethered my mobile device to my Xbox numerous times, using various connections depending on the desired results and I'd like to mention the results here. Not every method will operate in the same manner.
For example, bridging the network either tethered or wireless is the simplest way to connect your Xbox to Xbox live via mobile device. However, using ICS (Internet Connection Sharing) also allows the host computer to access internet while the Xbox is also connected. You can also fool the NAT compliance with the server by manually opening ports. Meaning, a user can play without restriction on Xbox live, with all the undesirable gaming impact forced upon other players on the same server. However, this is much more difficult to achieve, and is not as stable a connection as bridging. This connection is also very prone to hacker attacks, especially if you do not know how, or which ports should be opened for configuration.
I should also mention, that even before attempting... I recommend the user obtain UNLIMITED mobile internet access. Only a small handful of carriers even offer it, and usually their requirement is paid contract mobile service for 5+ years. But otherwise, a user will incur overages on their mobile plan... I use easily 20GB in less than a week connecting my Xbox to my mobile device, it is a bandwidth hog.
The steps for ICS and bridging are very different, and even different depending on OS. If you're attempting ICS be prepared for hours of troubleshooting, even then your mobile carrier may begin to restrict your subnet mask, your allowable max IP count, and even begin issuing a temporary IP that renews every hour to kick off devices. After two days of use, I experienced all these attempts to minimize bandwidth consumption, requiring me to adapt as various technological obstacles were electronically dropped on me. Unless you have a degree in communications technology, do not attempt an ICS... you will be fighting your own OS, as it seems Microsoft did not develop nor refine any user features for this function, in addition to your mobile carrier once your usage is audited.
To bridge your network, connect your PC to your mobile device and establish internet connection via tether or wireless. I achieved this using the stock tethering app, not PdaNet, or any other internet connection app. Then connect your Ethernet cable to your PC and Xbox, wait one moment for this to resolve IP address', it should come across as an unidentified network on your Ethernet adapter. Verify the devices are connected, view devices on computer, verify that file sharing is enabled but the internet connection for your mobile device is NOT shared. Or, run command prompt and type, 'ipconfig/all' and confirm the media connections enabled have IP address' assigned. (Note: a IP of 169.254.xxx.xxx to the Xbox is OKAY! If you have an IP of 198.162.x.x then you may actually be already to go through ICS! DO NOT continue to bridge connections if a 198.162.x.x is automatically assigned to the Ethernet connection. But, popular internet myth is a 169.254.xxx.xxx IP means no connection, THIS IS NOT TRUE! It means, no connection to internet only to local, but that's okay... we haven't bridged connections yet!)
Open Network and Sharing options, select both active networks, the internet connected network and the local one to the Xbox, right-click, and select 'bridge networks'. Give it about 2-5 minutes to bridge the connection. And attempt to log-in to Xbox live. The first attempt will not succeed (none of mine have), but after troubleshooting wired connections through Xbox it should resolve the network connection on the first attempt. It seems, this is a way of connecting without restarting the Xbox... I believe the network adapter for the Xbox resets before each attempt during troubleshooting which will resolve the connection.
Hope this information helps, and answers any questions you might have. It's very possible to achieve, in a variety of different ways, both tethered and wireless, with or without a router. Some connections are easier than others, but the end result SHOULD always be the same... with your carrier or your wallet screaming for wireless mercy.
Have fun folks!