Implement user/usergroup level access to records in database (on application level)

Answer 1

why not use an additional table relating Contacts and UserGroups? e.g.

ContactsAccess

int UserGroups.Id (FK)
int Contacts.Id (FK)

You could use a special value (e.g. zero (0)) to indicate unrestricted access ,or you could modify the Contacts table to indicate the permission type.

Answer 2

The way I'd probably go about it is a table similar to the following (MySQL):

CREATE TABLE `ContactsVisibleTo` (
    `ContactID` INT NOT NULL ,
    `Type` ENUM( 'User', 'Group' ) NOT NULL ,
    `ID` INT NOT NULL
)

A unique or primary key over all three fields probably isn't a bad idea either. The switch between public/private should be a field in the Contacts table.