You need to digitize the boundaries (assuming a search online has drawn a blank for any existing datasets - that would be my first port of call! EDIT - On that note, I just found this link which may be worth a look).
To digitize the boundaries, there are several approaches you can use but I would start by creating a line-dataset that represents the boundaries. At the coastline, extend the boundaries into the sea so they cross the coast. Many boundaries will follow rivers and you may be able to use a suitable rivers dataset (eg. the Free OS Strategi or VectorMap data - allowing for changes in the course of the rivers over time - the river may form a starting point that you can edit to match your underlying map). These rivers need to be pulled in to your boundaries layer obviously. For other boundaries just digitize by making your boundaries layer editable, select the new feature tool and simple 'draw' the line.
Once you have all your boundary lines (all extending out to sea where they meet the edge of coastline). Active the Processing plugin (comes as standard in QGIS - if you can't find it go to Plugins and activate it there). Find the SAGA Polygon-line intersection tool and intersect your UK coastline with the boundaries. BTW you can get a Scotland only coastline from OS for free in their Boundaries data (OpenData).
Finally, you will need to supply attributes for your counties.
This method presupposes that your coastline is a polygon data set. If not you can still intersect the lines and then assemble polygons but a better approach is to get a free polygon data set from OS OpenData.