I would assume you would need to write a python script that will parse through all features within that shapefile.
Each time it comes to a new feature, it would need to check for a unique id. If it doesn't exist, it would create one.
Next, it would run a query to check for features that... either share a boundary, common line segment, etc... There are options in the select by location tool in ArcMap. They should be accessible in python, too. With those features, it copies over the unique id to those features and moves on.
Eventually, it should get to the point where all features that meet the spatial query you are using share a common unique id.
I am assuming that the topology isn't incorrect, and that there aren't small spaces in between polygons too.
Hopefully that points you in the right direction or gives you an idea.
The way I would try going about this is using the Select by Attributes tool/script to select a feature based on the FID (just a way to work yourself through the features.. start low and move up) and if it lacks a unique id.
From there, I would use the Select By Location tool/script to add to current selected features within the same layer that either touch a boundary or intersect. Here I would check what version of ArcMap you have and what options are available. The ESRI documentation has some decent information for each version.
Now to actually work with the selected features seems a bit tricky. Check out this post (http://forums.arcgis.com/threads/43214-select-by-location-and-calculate-field-from-update-cursor-row-help) since it has details on ways to access the selected features and other suggestions. There is also another suggestion from (use a selection of features in ArcMap in Python script). Each of these does it in a different way, but they should provide you an idea of how to go about doing it.
From there, you use the Update Cursor to update the unique id field to whatever you'd like and loop until there are no more features that need updating.
I am sure there are some things I am missing and some features that may not be selected in this process. I would suggest trying it out and seeing what the results are then adjusting the selection process in the select by location part. A couple of tweaks and maybe an hour or so of coding/reading should get you on the right track.
It might be easier to try building this visually in Model Builder since you can just drag and drop tools and use the 'magic wand' to connect them. It might make flow easier to visually see.
For the Select By Attribute, Select By Location, and Update Cursor information, just Google arcpy and the name to find the ESRI documentation. I can't post more than 2 links. Sorry for no snippet, but the work flow should get you started.