Building a gps system
"Is it possible to do it?"

Well... everything is possible :-)

"Does GPS require Internet connection?"

GPS doesn't require internet. A GPS receiver (e.g. http://www.modulestek.com/prodts/GPS/Mars740-mini/Mars740-mini_SPEC.pdf) is connected to the reading unit via USB or a RS232 interface. The protocol is very simple. However it only provides latitude and longitude. If you want to have an address, map data is required (for this you would need internet - or a large memory). 

And of course such a system requires good signals from the GPS satellites.

"What do I need?"

First you need a GPS receiver (see above).

Second, you need a microcontroller unit which runs your application and does all the control of the external units.

Third, you need a GSM module (e.g. http://www.exp-tech.de/Shields/Wireless/GSM-GPRS/adafruit-fona-mini-cellular-gsm-breakout-sma.html) to send a message.
Don't forget the antenna for connection to the mobile communication network.

Fourth, you need a power supply. Ideally it has a battery which can be reloaded when driving.

As you may see, if you put all this together you are far from the "smallest thing possible".

Actually any modern smartphone could be enough. Mount it "invisible" under your saddle, connect it to a bike charger, find the proper App and that's it - although it might not be the smallest solution.

I don't know any, but I'm sure there are products off the shelf that fulfil your requirements, designed and developed by experienced engineers, and thus smaller and maybe cheaper than what you ever could achieve on your own.