IP and MAC are not good ideas, because:
- Many users can share the same IP address, e.g. when behind a NAT.
- You have no way of accessing the MAC address of the client, unless you have special software (not an ordinary HTTP server) and you operate on a LAN. Or you exploit some security bug in browser, but that does not count ;)
Setting a cookie with a uniquely generated value is a good idea, but be aware that cookies can be turned off and erased by the client. As of legality, as long as you declare the usage of cookies and you don't do evil things (counting unique visitors is ok), you are safe.
If you assume that a client with no cookie is a new visitor, then you don't need neither a database nor a unique value in the cookie, simply check if the cookie is present or not and set it. If you want to get more information, then, yes, you will have to keep track of unique values in cookies.