Query parameter checking for related list size

This will give you all accounts with no Contacts

list<Account> accs = [Select Id, Name, yourOtherFields 
                      From Account 
                      Where Id Not In (Select AccountId from Contact)];

No, it's not possible to filter a SOQL query on the number of related objects. Ideally we could do something like this

SELECT Id FROM Account WHERE COUNT(Contacts__r) = 0

As @SF_Ninja pointed out you can query all contacts in the org and then query all accounts that aren't related to them. However that'll be difficult to scale for medium to large orgs (you only get 50K query rows at this time so anything over that and your broke).

If the child object had a master detail relationship with the parent it's easy to create a rollup summary field with a count of the child objects which you can then filter on. For non-master detail relationships you can code a trigger to do your own rollup, or use Rollup Helper to create one with points and clicks.

Of course, this is now easy to do with Salesforce reports using the new cross filter. Just create an account report and add a filter that it only returns accounts without contacts. Now that the new analytics API is out, you could in theory pull that into an Apex class with a big of legwork (requires parsing the resulting JSON, and dealign with the nuances of connecting to a salesforce webservice in APEX)