A block with a random image from Flickr with "search tags = node terms"

The block 'User photos corresponding with a node's taxonomy term, location and/or date field' should do what you want. Use the keyword public for the user to grab CC licensed public photos. Options like sort order (e.g. random) and the taxonomy vocabulary to use can be found in the block configuration.

You can change the license restriction for 'public' queries at admin/config/media/flickr (Global options). You won't have legal issues even with copyright images. Embedded images aren't copies and are not on your server. However, recommendation is to make sure you can be contacted through your site and remove images if requested.

In the Block options on the same page select 'Hide empty blocks (no media found)' in case no photos correspond with the criteria.

If you enable the modules Taxonomy, Date Popup (part of Date) and Geofield before a first time install (or after uninstall) of the Flickr module, you get right configured fields for your nodes automatically that allow not only to filter on taxonomy terms, but also on a location or date. Furthermore, this functionality does not only apply on Flickr Blocks, but also on Flickr Filter. For example the shortcode in a node [flickr-user:id=public, size=q, num=6,location=48.867556/2.364088, date=2015-01-11, filter=interesting, sort=views] will produce an album 'Most viewed, most interesting Flickr photos near 5 Place de la République, Paris, France taken on 11/01/2015' ('Je Suis Charlie' manifestation at Paris last January). Ideal for news sites. Remember that you can use Flickr shortcodes also in a custom block, but obviously that wouldn't be dynamic as the provided Flickr user blocks (you have two of those).

Read the docs but if you have additional questions or I misunderstood the one above, don't hesitate to let me know.

Thanks.

Nice.