Excluding posts with certain value of meta_key keeping posts without that meta_key

You’ve almost got it – it’s just a problem with logic. What you’re basically saying is “get posts that don’t have this meta key, or where this meta key isn’t equal to ‘dhaka'”. The problem is, posts without that meta key at all… also aren’t equal to ‘dhaka’, so therefore they match!

You can fix this with a nested meta_query, using an AND relation, to check that the key also exists if you’re going to compare what it isn’t equal to. Like this:

$args['meta_query'] = array(
    'relation' => 'OR',
    array(
        'key' => 'wpse_city',
        'compare' => 'NOT EXISTS',
    ),
    array(
        'relation' => 'AND',
        array(
          'key' => 'wpse_city',
          'compare' => 'EXISTS',
        ),
        array(
          'key' => 'wpse_city',
          'value' => 'dhaka',
          'compare' => '!=',
        )
    )
);

You also don’t need to provide a value anymore when you’re using EXISTS and NOT EXISTS – this was due to an old bug. See the WP_Meta_Query documentation for more information on this.