If an already existing fleet (737-800 and 900 without winglets) is thinking of a winglet modification, is that possible without regulations? Or what are the regulations?
In the U.S., changing anything on the wing is considered to be a "Major Repair/Alteration" according to the FAA (FAR Part 43 - Appendix A)
To make those changes, this form - http://www.faa.gov/documentLibrary/media/Form/Form_337.pdf needs to be completed.
As you can see, it requires a certified mechanic to handle the work after which a person with Inspection Authorization would approve the aircraft for return to service.
A little extra reading - Who can perform different maintenance checks?.